What is the relationship between computation in CA and Turing computability?
Contributions by:
Bruno Martin <bmartin@essi.fr>
If you agree with the classical Turing computation, a elegant way to prove
the equivalence between TM and CA is as follows.
First, define acceptable programming systems [1] :
A programming system is a listing which
includes all of the partial recursive functions of one argument over N. A
programming system is
universal if the partial recursive function such
that
for all i and x is itself a partial recursive function ; that is
if the system has a universal partial recursive function. A universal
programming system
is acceptable if there is a total recursive function c for the composition such
that
for all i and j.
Then say that machine on the
input x computes
if
is defined and divergent otherwise.
TM have been proved to be an acceptable programming system [1] and I have
proved that CA form also an acceptable programming system by designing a
universal CA and a total recursive function c for the composition in [2]. The
Universal CA improves a previous intrinsic universal CA of Albert and Culik [3]
where intrinsic means that the universal CA serves as an "interpreter" for CA.
That is, the universal CA given the "code" of a CA A and the input x simulates
the behavior of A on input x.
At last, we use the Roger's isomorphism theorem [1]:
For any two acceptable programming systems there exist a bijective total
recursive function which translates the first one onto the second one.
And we conclude that CA and TM are of the same power.
A CA simulator which models self-replicating CA's is available. It runs on a
Unix Sparc platform and has a marvelous graphics interface. The simulator is
called xca and was written by H.H. Chou at the University of Maryland. It is
available by anonymous ftp: ftp.cs.umd.edu:`pub/dtr.tar.Z'
A "reversible" cellular automaton in which various objects can self-reproduce
in a very simple fashion is described in:
K. Morita and K. Imai, ``Self-Reproduction in a Reversible Cellular Space'',
Int. Workshop on Universal Machines and Computations, Paris, March 1995.
The file of this paper (sr.ps or sr.dvi) is available at: paper
The related URL where self-reproducing processes can be seen as Quick Time
Movies is
Moshe Sipper has recently been studying such CA under the heading
"non-uniform CA", investigating issues of evolution and
computation. Moshe Sipper introduced two models [here].
The first model consists of non-uniform CAs evolving
in various environments, while the second consists of non-uniform CAs
with enhanced rules, where complex organisms were presented. This latter model
has been expanded in [Sip95b]
which discusses multi-cellular organisms as well as evolution in various
environments.
In [Sip95a]
the issue of universal computation was addressed. The computation-universal
system presented is simpler than previous ones, and is embedded in the minimal
possible two-dimensional cellular space, namely 2-state, 5-neighbor (which is
insufficient for universal computation in the uniform model). The space studied
is quasi-uniform, meaning that a small number of rules is used (the final
design consists of just two rules which is minimal), distributed such that most
of the grid contains one rule except for an infinitely small region which
contains the others.
How are transients measured in CA?
There are at least two definitions of transient length:
1) The time to reach a cycle in a finite CA with periodic boundary
conditions.
and
2) time for statistics to settle to a fixed point or limit cycle in a
(potentially) infinite system.
The relationship between the two is subtle. For some discussion of definition
1), you can look at [GL95][Gut91a]
(and for definition 2 [gutowitz95]).
These three articles can be accessed via the web here.
Reynolds: The Boids flocking model was described in a
SIGGRAPH 87 paper. Its not available online, but I can send
hardcopy to interested parties. The model has been used in
some computer animation and for special effects work for
feature films.
It is not actually a CA model, its some other kind of
moveable automata.
There is a beginning of a Boids home page on the web:
Boids.
A-Quarium is a fish tank simulator based on an A-Life program 'Boids' by
Craig Renolds. A boids-like screen saver (requires Windows). A-Quarium.
Bauchau, Vincent <bauchau@cto.nioo.nl><taob@gate.sinica.edu.tw> Brian Tao
"Computronium" is a hypothetical substance in which each processing cell of a
CA is reduced to atomic scale and arranged in a crystal lattice.
See:
Ivan Amato. Speculating in precious computronium: a new computer embodies an
architecture that - to its creators - mimics the structure and dynamics of
physical reality. (Norman Margolus' and Tommaso Toffoli's Cellular Automaton
Machine 8, or CAM-8). Science, August 23 1991, v253, n5022, p856-7.
"Garden-of-Eden" is a somewhat whimsical term attributed to John Tukey,
coined at a time when John von Neumann was designing a self reproducing
automaton and Edwin F. Moore was perfecting a theorem which asserted that there
were configurations for an automaton which could only exist initially.
Mapping a finite set into itself, this result is not surprising. If some
elements (configurations of the automaton) have many courterimages (ancestors),
others will have fewer, and some may have none; it is simply a matter of
counting. But cellular automata deal with infinite sets, so considerably more
work has to be done to establish the theorem.
Even so, for most rules, it may not be possible to reach a decision as to
whether an arbitrarily given configuration has an ancestor or not, even if it is
already known that ancestorless configurations exist. This can easily turn into
a discussion of computability.
How important is synchronicity in CA?
Contributions by: Bill Tozier <wtozier@mail.sas.upenn.edu>
Shan Duncan <duncan@loris.cisab.indiana.edu> Joel Rahn
<RAHNJ@vm1.ulaval.ca> Erik Winfree
<winfree@druggist.gg.caltech.edu> Jordan B Pollack
<pollack@dendrite.cis.ohio-state.edu><chaos@gojira.Berkeley.EDU> Jim Crutchfield Eugen Leitl
<ui22204@sunmail.lrz-muenchen.de><worsch@ira.uka.de> Thomas Worsch Francisco Jimenez
<jimenez@cica.es><bjo@fwi.uva.nl> Benno
Overeinder <POLSTAB@MIZZOU1.missouri.edu>
Cellular automata are discrete, regular, and synchronous. Those interested in
cellular automata as such begin with the CA definition and work to discover the
implications of these properties. Those interested in using CA as models in the
natural sciences, on the other hand, begin with a natural system in mind and
work to discover how well the behavior of their system can be approximated by a
CA model. Both those interested in abstract properties of CA and those
interested in applications find discreteness and regularity uncontroversial
compared to synchronicity. Many of the unique features of cellular automaton
dynamics can be traced to the synchronous update of cell-states. An abstract of
some of the discussion on this matters follows.
An example of the importance of synchronicity in CA dynamics is the work of
Chate and Manneville [CM91]
on collective behavior in CA and coupled-map lattices. This behavior is of major
importance in the field of dynamical systems. Indeed, before this work appeared,
some had "proved" (in the physicists sense of proof) that such behavior was
impossible. Collective behavior seems to be stable to all sorts of perturbations
of the model except giving up on synchronous updates.
The paper by Huberman and Glance [HG93]
supports the opinion that the organization of the subunits in a model must
approximate the organization of the subunits in the system to be modeled, and
the dynamics of the model must be a good approximation of the dynamics in the
real world. [not always the case for CA]
For some examples of CA models in the natural sciences which "work" see
Ermentrout and Leah Edelstein-Keshet [EEK93]
and the section on lattice-gas automata.
An early reference: [T.E84]
They investigate Wolfram's CA rules using a probabilistic method for updating
cells. Some of the rules give patterns, some don't. From the Abstract: "...some
of the apparent self-organization of (CA) is an artifact of the synchronization
of the clocks."
Greenberg-Hastings type models of reaction-diffusion systems do a decent job
of arriving at the same qualitative spatial structure as the real phenomenon
(e.g. Zhabotinsky reaction), in this case stable rotating spirals of activity.
However, if the Greenberg-Hastings model is executed with asynchronous update,
mayhem breaks loose; rather than, say, one stable spiral, the spiral fractures
into a thousand jumbly pieces.
Thus, synchronous and asynchronous update schemes may lead to vastly
different results, and a modeler must be careful in using either one. But the
real issue is is not at all new - modelers must be explicit about what
assumptions they make when designing their model. In CA, conserved quantities
and conserved properties of the system have vast consequences on its subsequent
evolution, and must be carefully analyzed.
For example, in the Greenberg-Hastings model, a conserved quantity is that
the winding number of every closed path remains unchanged over the course of the
evolution. This property is also true for simple PDE models of excitable media.
(In more complicated versions of both models, unfortunately, this breaks down in
some cases.) But the point is that the CA model is decent because the conserved
properties of its evolution are right. For G-H, single local applications of the
CA rule may not preserve the conservation law, and thus a radically different
steady-state is seen in asynchronous simulations.
In the neural network community there is the same sort of concerns with
regard to synchronicity of updates. People implementing parallel machines are
interested in synchronized systems, while others whose models depend on a
sequential update rule will argue from the biological plausibility of
asynchronousness.
A typical "biological plausibility" statement is found in Daniel Amit's book
modeling brain function (p. 80):
to reiterate, the asymptotic behavior of the network, on which we
focus our interest, may depend on the dynamical procedure, but such dependence
is unwarranted because no particular procedure is a faithful representation of
the activity in the biological network. We therefore look for asymptotic
properties which are insensitive to the updating procedures
Synchronization problems (FSSP etc.) and patterns transformation/recognition
in CAs are the major issues of this readable book: [VT79],
which also contains an extensive bibliography.
See Scott Page <scotte@mrfloods.caltech.edu> for a draft ms.
on incentive-based asynchronous updating in CA.
Which computations can 1D CA perform?
Contributions by: Peter Ruff <rzuw009@rz.uni-wuerzburg.de>
Ruff: I have set up a 1d2n22s CA which performs binary multiplication
by 79 transition rules. Result of n * m digits is available after maximal n + m
+ 2 steps.
Contributions by: Mark A Biggar <mab@wdl39.wdl.loral.com> Rudy
Rucker <rudy@autodesk.com>
Biggar: Sure if you allow for more then 2 states and/or neighborhoods
greater then 3 wide.
First I work with more then 2 states and then with wide neighbor hoods.
Suppose that you have a N state M symbol Turning machine, this maps to a 1D
(N+1)*M state 3 wide neighbor hood as follows: M of the states correspond to
tape squares were thr turning machine read/write head is not located and are
direct mapping of the turning machine's tape. The other N*M states represent the
tape square where where the read/write head is located. A state at that position
represents the tape has one of the allowed symbols and the machine is in a given
state giving N*M possibilities. Using a width 3 neighborhood then most cells are
quiescent and don't change only the three cells with on of the M*N states in
their neighborhood can change in a given time. Defining the rules based on the
original turning machine is obvious.
Now if you start with a Universial Turning machine you end with a Universal
Automata.
w to go back to a Binary Automata. If I have N states in the above Automata
it can be easily mapped to a binary automata with a neighbor hood of width
4*N+11 as follows: For now assume that there are only 4 state (to make the cases
to be examined small) the each cell in the 4 state 1D automata will map to a row
of 9 cells like so:
These patterns will overlap 1 cel on each end so the turning tape would
be represented as:
Using a 27 cell neighborhood it is easy to define rules that correspond to
the original 4 state automata. the 111's in the pattern act as registration
marks
the other cells can determine which position they are in. The original set up
of the 1D automata does not need the registration marks already in place out to
infinity they can propogte themselves out automatically and keep ahead of the
non-empty part of the tape with ease. More compact coding are possible, but this
one is wasly to explain and gives a automata that runs at the same speed as the
original.
There is a 4 symbol 7 state Univ Turing machine described in ``Computation:
Finite and Infinite Machines'' by Minsky.
Rucker: It is pretty simple to model a standard turing machine as a 1d
CA. If the TM uses k symbols and n states, then you can make a 1d CA with
states per cell. Most cells are in the state i,0 for some
.
The cell where the ``head'' resides is in the state i,j for some
and
.
The update rule is for each cell to stay the same unless the
cell is where the ``head'' is or is a cell that the ``head''
is about to move into.
Postscript: a 1D, 2-state, r=1 CA is now also believed to be universal - rule 110.
I will assume that a ``configuration'' comprises a N x N square of symbols
0,1 with the sites outside of this square assumed 0 (this is what I would term a
``finite'' configuration.
One can ask:
Is there a configuration which maps onto this configuration?
Is there a finite configuration which maps onto this configuration?
In one-dimension there are much-explored algorithms which answer to both
questions. Fundamental to the algorithm is the existence of bounds based on the
parameters of the CA rule (specifically the states per site and number of sites
distant the rule takes into account, Wolfram's k and r). Based on these one
finds a bound phi(N) (recaall N is the initial size of our finite neighborhood)
for which if there is any finite predecessor, there must be one of length at
most phi(N). The first question is slightly more complicated, but the procedure
is similar.
In two dimensions both questions are undecidable. This means that the
function phi while it still exists abstractly (there are still a finite number
of rules with a given k and r), grows faster than any recursive function.
The proofs of the above statements are not difficult, and relate to the
undecidability of the tiling problem for Wang tiles.
Note that none of the above discussion means that the problem cannot be
solved in the specific case of the game of Life. It would be impressive to
demonstrate such a technique, as Life is sufficiently complicated to be
computationally universal.
What are some reversible rules?
Contributions by: Bruno Durand <bdurand@ens-lyon.fr>
The following reversible cellular automaton has been presented by Jarkko
Kari. It has 2 neighbors (the cell itself and its right neighbor). The set of
states is 1,2,...,n. The local transition rule f:
What is known about periodic orbits in CA?
Contributions by: Lyman Hurd <hurd@math.gatech.edu> John
Pedersen <jfp@goedel.math.usf.edu>
Hurd: In a recent paper I used the terms temporally and spatially
periodic, but informally I sometimes just say horizontally or vertically
periodic. Here is an (I think) interesting result:
Assume that a 1-d CA has a quiescent state. I will (informally) call a
configuration ``trivial'' if it evolves to the all-quiescent state which I will
assume is a fixed point. A CA for which ALL configurations are trivial, will be
called nilpotent.
1) A CA has a non-trivial temporally periodic orbit if and only if it has a
non-trivial spatially periodic orbit (one half of this proof is easy).
2) There exists a cellular automaton for which EVERY periodic (spatially or
temporally, equivalent by (1)) orbit is trivial BUT for which not every
configuration is trivial.
This example (OK I did not give an example I just stated it exists-in fact
Kari, Culik and I have a specific example with 17 states) means that there can
be dynamics missed entirely by the restriction to spatially periodic
configurations no matter what the finite lattice size.
PART II:
The following proof is due to K. Culik. To show that a finite configuration
must have an (eventually) periodic predecessor, if it has a predecessor at all,
consider the following state:
Assume that the rule has radius one (the proof goes through in general with
obvious modifications). Denote by k the number of states per site.
has a predecessor:
Lining them up:
Consider a window which is two high and three wide (if R is the radius,
2R+1), sliding over the pair of configurations. Start with:
0 0 0
and continue to the right. There are only
possible values so at SOME point the list must have a duplicate, i.e.,
0 0 0 0 0 0
Now we can replace d with a configuration periodic on the right by defining:
if
and otherwise
A similar trick works on the left and QED. The same technique shows the
stronger result (of Golze) that periodic configurations must have periodic
predecessors.
See also: [Ped92]
which derives algebraic conditions for all orbits a CA being periodic.
It is true that initial conditions in cellular automata with circular (1D) or
toroidal (2D) boundary conditions form a special case of all configurations. In
fact, the dynamics on a fixed torus/circle form a compact subspace. The set of
all possible spatially periodic configurations is more problematic topologically
as it is neither open nor closed and is dense.
However, it follows from Kari's work on the undecidability of the nilpotency
problem that knowing the eventual dynamics of all periodic configurations does
not suffice to tell you the entire behavior of the CA.
The following theorems are shown constructively in: L. P. Hurd, J. Kari, K.
Culik "The Topological Entropy of Cellular Automata is Uncomputable" which
appeared in Ergodic Theory and Dynamical Systems (I am unfortunately separated
from my files and do not remember the exact issue. Anyone interested can email
me directly):
I will state the results in 1-D. They all apply a fortiori to higher
dimensions. In general, undecidability results get easier as dimensionality goes
up. The following conditions are equivalent:
1) A given (1-D) CA has no temporally periodic orbits except for the
quiescent one.
2) Every spatially periodic state evolves in finite time to the quiescent
state.
One of these implications is pretty easy. I will leave it as an exercise.
However we gave a counter-example of a nearest-neighbor rule with 17 symbols
which showed that 1) and 2) fail to imply:
3) Every configuration evolves to the quiescent configuration.
A compactness argument shows that 3) holds if and only if:
4) There exists a constant N such that every configuration evolves to the
quiescent configuration in at most N time steps.
In all of the above configurations are NOT assumed to be finite (of compact
support).
Put simply, any spatially periodic initial condition which you set for this
rule however big the spatial period will eventually die out. However, there is
shown to exist infinite configurations which are not periodic which persist
indefinitely. The space-time diagram of one of these configurations forms an
aperiodic tiling of the plane.
A generalization of this rule (which came in a mysterious way from Penrose
plane tilings; more mysterious when you remember we are still in 1D), produces
CA's with arbitrarily high topological entropy (informally arbitrarily much
dynamics) for which the dynamics lies entirely off the periodic orbits.
What are subshifts of finite type/sophic systems?
Contributions by: Mike Boyle <boyle@msri.org>
Historically the study of SFT's got a lot of impetus from hyperbolic
dynamics, where SFT's are the natural symbolic dynamics for making use of Markov
partitions. You can do a lot of your analysis of equilibrium states and periodic
points on the SFT. (The analysis of equilibrium states on sofic shifts is much
harder.) This is an historical reason for the focus on SFT's but it is also a
mathematical one. It is completely reasonable on mathematical grounds that SFT's
should be distinguished as the most important subclass of sofic systems. It is
for SFT's that finiteness conditions, coding constructions and algebraic
invariants are most transparent; and one key to studying a sofic system is to
understand how its properties relate to those of the SFT underlying the minimal
deterministic finite automaton for the regular language of the sofic system.
But: I think Prof. McIntosh's consideration of sofic systems as a fundamental
class is absolutely correct. It is in various ways a more natural class than the
class of SFT's. For example, it is closed under quotients and unions. More
fundamentally, it is much more naturally ``the'' class of subshifts with a
finite presentation than are SFT's. I think this represents the consensus among
workers in symbolic dynamics.
Prof. McIntosh's interest in sofic systems is especially gratifying to me, as
I work in symbolic dynamics myself and have formed the impression that most
workers in cellular automata regard even SFT's which are not full shifts as
esoterica. It seems to me that symbolic dynamics provides at the least tools and
a perspective useful for some problems about automata, but these have not been
much used in c.a.
Just one example: from the symbolic viewpoint the c.a. insistence that its
automata be block codes on full shifts (versus block codes on SFT's or other
subshifts) seems unnatural. The latter viewpoint finds some justification in the
recent work of Alejandro Maass <ams@lumimath.univ-mrs.fr>. He
uses techniques of symbolic dynamics to show that any endomorphism f of a mixing
SFT S is the restriction of some c.a. map which has image S, under the necessary
assumption that S has a fixed point. (He also has more sophisticated and less
easily stated results about c.a. limit sets and dynamics.) In other words, to
understand the limit dynamics of c.a., you must understand the limit dynamics of
endomorphisms of SFT's.
This is not just a problem, it is also an opportunity, because tools for
studying SFT's can contribute some understanding.
What is the mean field theory?
The mean field theory is a way of approximating the action of a CA by a map
with continuous parameters. The approximation is derived by assuming that the
states of cells at different locations in space are not correlated. A simple
version of the mean field theory is the
parameter of Langton, more general versions, which take into acount spatial
correlations, have also been developed.
A CA is injective if its global function F satisfies
implies . This, of course, is the general definition for functions. In the
case of CA a stronger result holds (reference?).
Theorem A CA is injective if and only if it is reversible (i.e., bijective).
Surjectivity for cellular automata (although not in general) is a strictly
weaker condition that for all y there exists x such that .
For 1-dimensional CA there exist well-known algorithms to determine
surjectivity and injectivity (by an algorithm is meant, you hand it a rule table
and in guaranteed finite time the answer comes back for all possible 1D CA).
In 2 and more dimensions a highly non-trivial result of Jarkko Kari shows
that the question is undecidable. The question is linked in a deep way with
Berger's Theorem about the undecidability of tiling by Wang tiles.
It is trivially verifiable when two rules invert each other. Kari's Theorem
then implies that there must exist 2D rules for which the complexity of
describing its inverse vastly exceeds the complexity of the rule itself. If we
take r (the radius) and a rough determinant of complexity, for any recursive
function phi, there must exist a rule with radius r whose inverse rule has
radius greater than phi(r).
Can one decide if a 2D rule is reversible/surjective?
Jarkko Kari has proven that the reversibility question for 2D or higher CA is
undecidable. It is true in all dimesions that a rule is reversible if and only
if it is injective. Kari also has proven that the surjectivity problem is
undecidable (a necessary but not sufficient condition for reversibility).
As he points out, the two questions are somewhat different. In the case of
surjectivity one can demonstrate its lack by giving a finite configuration which
one can test exhaustively cannot be reached. This provides a semi-procedure even
though no corresponding semi-procedure can be found in the other case. On the
other hand, it can be finitely demonstrated that two rules indeed invert one
another, so there is a semi-procedure to show that a CA IS reversible.
One way to show decidability in the 1D case for both questions consists of
proving recursive bounds on how big a string one would need to find to show a
counterexample to surjectivity or how large a radius rule one needs to examine
to prove reversibility. In both cases such a bound (as a function of the number
of states per site and radius) exist, although I do not recall their exact form
(I used to know, step in anyone who remembers). Kari's proffs suffice to say
that there is no such recursive bound for 2 or more dimensions.
Where do I read about reversible cellular automata?
Contributions by: Harold V. McIntosh
<mcintosh@uapnx1.dgsca.unam.mx>
The name most prominently associated with reversible
cellular automata seems to be Tommaso Toffoli; his most
accessible work is probably [TM87].
Whereas the book describes a number of reversible rules for
the CAM-6, Edward Fredkin's analogy with second order
differential equations is the only background theory
mentioned, in section 14.2. The Margolus neighborhood,
strongly featured in the book, was evidently created to
facilitate reversibility.
In turn, Fredkin has acquired widespread fame for the replication properties
of the <exclusive or> when taken as a rule of evolution. However, it is
difficult to encounter a single reference which can be cited, for either Toffoli
or Fredkin, that can be fairly said to present their own views. Martin Gardner
reported Fredkin's replication in his second article on Life in 1971, reprinted
in [Gar83]
thereby giving the idea worldwide publicity.
Perhaps the computer science community's outstanding early contact with
reversible automata was [AP72].
Non-reversibility, in the form of the Garden of Eden, seems to go back to [Moo70].
What seems to be quite remarkable is the degree to which such issues were worked
out by mathematicians, within the context of symbolic dynamics, during the
1950's and 1960's. The fundamental paper in this respect is [].
It is in fact a summary of quite a bit of work, carried out by Hedlund
himself and others. One of their important concepts is a "subshift of finite
type" which is a biinfinite string of symbols from which a certain finite set of
words has been excluded. Sort of like excluding all the 1's from trinary (i.e.,
0, 1, 2) decimals to get the Cantor set. Shifting the decimal point in one such
number gives another.
Topology figures very strongly in symbolic dynamics, which
may have restricted its appreciation; on the other hand it
facilitates talking about limits and leads to a useful
measure theory and probabilities. The topology is such that
two strings are closer, the longer their central segments
which match up; it turns out that those continuous functions
which commute with the shift are each generated by the
transition rule for some linear cellular automaton. Thus
symbolic dynamics is an application of automata theory, or
vice versa. The two theories overlap, but have tended to
emphasize different features. Would a symbolic dynamicist
have discovered Wolfram's class iv on his/her own?
Subshifts of finite type arise from graphs whose nodes
are symbols and whose arrows show admissible sequences;
missing arrows result from the operative exclusions. Someone
realized that a much more interesting model resulted from
using the symbols as links among arbitrary nodes; the
publication generally credited for this is [Wei73]. It should be noted that the
language of his presentation is semigroup theory, not graph
theory.
Three papers by Ethan M. Coven and Michael E. Paul come from the same time
period: [CP74][CP75][CP77].
Several articles by Masakazu Nasu, written in the spirit of Hedlund's
symbolic dynamics, appeared in the late 70's and early 80's; perhaps the most
relevant is: [[Nas78].
Somewhat later the ideas were generalized to apply to flows through graphs:
[Nas82].
An early attempt to relate reversibility and Gardens of Eden and to use the
interplay between global and local mappings was [Ric72].
A somewhat later paper [SH77]
works out in considerable detail the relationships between injectivity,
surjectivity, and several other properties of cellular automata. Slightly
earlier, [Yak76] appeared.
The reasons for interest in reversible automata seem to have been varied. A
formal theory such as Hedlund's would naturally have been concerned with the
kind of details represented by surjectivity, injectivity, continuity, the
existence of limits, and so on; all of his results may well have been worked out
simply for the sake of presenting a thorough and complete theory. One would have
to ask him, or someone who was very familiar with his work.
Garden of Eden theorems seem to have resulted more as a counterbalance to von
Neumann's universal constructor; the reversible machines which they imply seem
to have been less of an issue than the fact that some specific automata were
<<not>> reversible, and the momentary confusion between the
implications of the two concepts. Consequently Toffoli seems to be a plausible
candidate to have been the first proponent of reversible automata as such.
His publications are not all that easy to track down, consisting of his
thesis, laboratory reports, contributions to conference proceedings, and so on.
However, [Tof77]
states that "an arbitrary d-dimensional cellular automaton can be constructively
embedded in a reversible one having d + 1 dimensions," and precedes to show how
to do so. This approach is different from Fredkin's, which merely uses an
arbitrary cellular automaton to construct another which is reversible, without
pretending to embed the original; indeed it usually does not. There is also a
joint paper, [FT82]
which goes into some of their mutual ideas.
What are the properties of CA when viewed as maps on the reals?
Contributions by:
<mcintosh@servidor.dgsca.unam.mx> McIntosh Harold V.-UAP Fred Dushin<fadushin@top.cis.syr.edu><nami@carpet.math.hokudai.ac.jp
NAMIKI Takao>
The transition function for a one-dimensional cellular automaton can be
viewed as a function from the non-negative reals to the nonnegative reals. With
a left boundary such a CA can viewed as a function on the upper half open
interval [0,1). (The problems that arise e.g. for a two-state CA, for real
numbers with terminating binary expansions can be avoided in a variety of ways
to ensure that reals have unique binary expansions.)
There are probably several ways of creating such a mapping, but the one which
seems to be most commonly used regards each semi-infinite configuration as the
k-nary (for a k-state automaton) expansion of a number in the interval 0-1. A
bi-infinite configuration fit into the two-dimensional unit square, leaving the
shift operation as Arnol'd's CAT-MAP.
For this purpose, it is very explicitly necessary to treat such things as
1.00000 and 0.99999 (or their k-adic equivalents) as lying far apart, and so
their natural topology is not that of the real numbers; in fact it is that of
the k-adic numbers which is a direct product of cyclic spaces. Near(k-adic)
seems to be near(real) but not necessarily the reverse, which relates the two
topologies to an extent. This discrepancy has caused much anguish, and seems to
be the historical reason for defining dynamical sustems in a certain way, and
not as sofic systems, which is the more inclusive concept.
Intuitively this topology regards configurations as being closer, the further
along their central segments agree; theoretically it makes the shift operation
continuous and the cellular automata become the manifestations of a continuous
map.
One of the most prominent figures in Symbolic Dynamics was Gustav A. Hedlund,
author of various articles and books. Pertinent to Cellular automata theory is
G. A. Hedlund, ``Endomorphisms and automorphisms of the shift dynamical
system,'' Mathematical Systems Theory3 320-375 (1969).
A good recent treatment is:
Roy Adler and Leopold Flatto, ``Geodesic Flows, Interval Maps, and Symbolic
Dynamics,'' Bulletin of the American Mathematical Society25
229-334 (1991).
An unique approach to such lines is shown in the following memoirs.
Masakazu Nasu, "Textile Systems for Endomorphisms and Automorphisms of the
Shift", to appear in Memoirs of A.M.S.
People who are adept at such lines of reasoning have proved many interesting
properties of dynamical systems, which can probably be traced through citations
to the two papers mentioned above, as well to the key words "dynamical systems"
and "sofic systems." In another direction, Peter Grassberger has studied
statistical properties of the resulting "plaid diagrams" as typified by the
following references:
Peter Grassberger, ``Long-Range Effects in an Elementary Cellular
Automaton,'' Journal of Statistical Physics45 27-39 (1986).
J. M. Greenberg and S. P. Hastings, ``Spatial patterns for discrete models of
diffusion in excitable media,'' SIAM Journal on Applied Mathematics34 515-523 (1978).
In the descriptions of LCAU there is a discussion of the
plaid diagram option; the programs will generate them and
some related figures, such as the "unit circles" of various
radii surrounding designated points.
Contributions by: Jan Hemmingsson <jan@manet.espci.fr>
There are three articles by Normand Mousseau on rule mixing;
Frustrated induced phase transition in high-dimensional deterministic
cellular automata I was in Europhysics letters end of 1994 or beginning of
1995. He finds some intermediate state by mixing two rules (periodic three and
periodic two).
On the phase diagram of frustrated (quasi-)periodic CA Oxford Univ.
OUTP-95-27S
Randomly connected CA: A search for critical connectivities Oxford Univ.
preprint
What are 'kinetic' CA?
Contributions by: Thomas Worsch <worsch@ira.uka.de>
If you allow
only integer coordinates,
some kind of local communication between the cells (e.g. each cell
``sees'' the states of the cells at neighboring coordinates) and
that a cell may split into two and that a cell may vanish,
then you get a model called ``systems of Turing automata'' (STA) in
Hemmerling, A. (1979): Systeme von Turing-Automaten und Zellularr"aume auf
rahmbaren Pseudomustermengen, EIK 15, 47-74.
With such a model you can simulate cellular automata and vice versa without
any loss of time. (The simulating STA seems to need cells at essentially at all
lattice points).
The ``advantage'' of STA is that you can investigate the ``hardware
complexity'', i.e. the maximum number of cells which are simultaneously existing
during a computation. Roughly:
maximum hardware == cellular automata
minimum hardware (i.e. 1) == Turing machines with one tape and one head
One can also find hierarchies of complexity classes.
See also:
Hemmerling, A. (1979): Concentration of multidimensional tape-bounded
systems fo Turing automata and cellular spaces, Proc. FCT 79, 167-174.
Worsch, Th. (1991): Komplexit"atstheoretische Untersuchungen an myopischen
Polyautomaten, Dissertation, TU Braunschweig.
What are some references on CA and symbolic dynamics?
Contributions by:
<mcintosh@servidor.dgsca.unam.MX> McIntosh Harold V.-UAP
NAMIKI Takao
G. A. Hedlund, ``Endomorphisms and automorphisms of the shift dynamical
system,'' Mathematical Systems Theory3 320-375 (1969).
Roy Adler and Leopold Flatto, ``Geodesic Flows, Interval Maps, and
Symbolic Dynamics,'' Bulletin of the American Mathematical Society25 229-334 (1991).
Masakazu Nasu, "Textile Systems for Endomorphisms and Automorphisms of the
Shift", to appear in Memoirs of A.M.S.
Which two-state, one-dimensional, reversible CA-rules produce non-trivial behaviour?
Contributions by: Burt Voorhees
<mcintosh@servidor.dgsca.unam.MX> McIntosh Harold V.-UAP
You might take a look at elementary rule 150 defined on a circular lattice
for which the number of sites is not a multiple of 3. The rule is reversible in
these cases, but for different numbers of sites, the inverse rule is different.
Non-trivial lies somewhat in the eye (or mind) of the beholder. Probably the
first publication along these lines was the article of Amoroso and Patt in 1972,
wherein they found by exhaustive search some (3,3/2) [four-neighbor] reversible
automata, and announced a general construction, something involving an xor of a
chain of states, to get a whole family of reversibles.
Somewhat later Fredkin conceived of a scheme for reversing automata (several,
in fact, but one of them was still confined to one dimension), but since it is
equivalent to using a cartesian product, the least you can get is a four-state
automaton.
Now and then searches have turned up other reversible 1-D automata, and the
topic comes up for discussion on CA-Mail fairly frequently. Now and then
articles devoted to the subject have been published, one of the most
comprehensive of which was authored by David Hillman; namely, "The structure of
reversible one-dimensional celluolar automata," Physica D 52 277-292 (1991). He
cites well-known transformation rules to reduce automata to radius-1/2
[two-neighbor] equivalents, invokes some further equivalences, and finally
announces a search scheme which will yield up all the reversible automata.
The question of reversible automata is tied into the theory of symbolic
dynamical systems, which is sometimes invoked in treatments of automata theory.
In that area, a paper of R. F. Williams, "Classification of subshifts of finite
type," Annals of Mathematics 98 120-153 (1973), is often mentioned, along with
the fundamental paper of G. A. Hedlund. The relationship is rather specialized,
and seems to require a certain amount of preparation and training to follow it
through.
Following what seems to be the relationship requires going back to the Atlas
of Wuensche and Lesser, in which they catalog the basins of attraction for all
the (2,1) autom. F. Williams examples for cycles up around 15 cells in length.
An algebraic, or at least matrix theoretical, approach to these basins can be
gotten from the A and B matrices, the connectivity matrices of the de Bruijn
diagrams of their automata. Matrix elements of products of those matrices tell
how many ancestors their corresponding configurations have, and thus define the
branching found in the trees of the basins of attraction.
For reversible rules, there can be no branching, and the basins are required
to consist of pure cycles. But there is a symmetry situation, in that permuting
the labels of the states of the automaton obviously can't affect their
reversibility, nor can forming Wuensche and Lesser's clusters. The result is
huge clusters, but Hillman seems to have found that there aren't very many
distinct clusters. This has some bearing on what one calls "non-trivial."
According to Williams, equivalence between shift systems (which would make
one of them reverse the other) depends on certain relations between the
connection matrices defining the shift, essentially these selfsame A and B
matrices. There are in fact three levels of relationships.
1) "topological conjugancy" suppose that M and N are connection matrices, and
that there exists a matrix R, possibly rectangular, for which RM = NR. That
means that R defines a mapping between nodes, which conserves links in the
(directed) graphs (of possibly different sizes) whose connections are given by M
and N. In addition there may be a matrix S (say, R transposed) for which MS =
SN, so that conservation of linkages goes both ways.
2) "strong shift equivalence" suppose as before that M and N are connection
matrices, but that they derive from a factorization in which M = PQ and N = QP.
Rather than saying that their graphs have image links connecting image nodes,
the two graphs are duals of one another. At least, that is the case in the
particular situation where P and Q define either functions or antifunctions, and
may be considered as a sort of generalized duality.
Simple algebraic manipulation shows that MP = PN and that QM = NQ (without
saying that P and Q are transposes).
3) "weak shift equivalence" Williams finds a modified
requirement, merely that there be a common power k to obtain
shift equivalence in the shift dynamical system. The origin
of this alteration seems to lie in the fact that a
connection matrix is a secondary consideration for dynamical
systems, and that a shift of length k may be required to
synchronize one system with another.
In any event, what
has to be understood are the possible equivalences between
matrices with integer coefficients, or even the more
restricted classes where the integers must be either
positive, or non-negative. Over the complex field these
relationships are easily satisfied, by appealing to the
Jordan Normal Form.
If m = u l v, where we use upper and lower case for the members of the pair,
and l is diagonal with uv = vu = (identity matrix) (life complicates with Jordan
blocks, but much is to be learned before introducing them), and M = U L V, with
UV = VU = (Identity Matrix). then candidates for r and s are r = Uxv and s =
uYV, where x any y are appropriate diagonal matrices.
One fundamental reality, whatever the field, is that PQ and QP have to have
common eigenvalues and related eigenvectors, with the exception of discrepancies
with eigenvalue zero. The same is true of topological conjugates, so if M and N
do not have common eigenvalues, P and/or Q must annihilate some vectors.
A consequence is that one should only aspire to construct a topological
conjugacy when the topological matrices have the same Perron eigenvalue (the
real eigenvalue of strictly maximum modulus which is the common heritage of all
non-negative matrices). Actually, any common eigenvalue would do, but the Perron
eigenvalue comes with a real (rational, for rational matrices) positive
eigenvector, nice if the mapping is supposed to be a function between point
sets.
The matrices x any Y can be manipulated to make r f(m) r = f(M) r, giving
weak [f(m) = ]
and strong [f(m) = m] equivalence under circumstances which look
suspiciously like requiring m and M to have eigenvalues which are either zeroes
or ones. If that were true, than the A and B matrices mentioned above would have
to share this property, and it would greatly simplify searching out reversible
pairs of cellular automata.
Have CAs been used in real analysis?
contributions by: <mcintosh@servidor.dgsca.unam.mx> McIntosh
Harold V.-UAP
The transition function for a one-dimensional cellular automaton can be
viewed as a function from the non-negative reals to the nonnegative reals. With
a left boundary such a CA can viewed as a function on the upper half open
interval [0,1). The problems that arise e.g. for a two-state CA, for real
numbers with terminating binary expansions can be avoided in a variety of ways
to ensure that reals have unique binary expansions.
There are probably several ways of creating such a mapping, but the one which
seems to be most commonly used regards each semi-infinite configuration as the
k-ary (for a k-state automaton) expansion of a number in the interval 0-1. A
bi-infinite configuration fit into the two-dimensional unit square, leaving the
shift operation as in Arnol'd's cat map.
For this purpose, it is very explicitly necessary to treat such things as
1.00000 and 0.99999 (or their k-adic equivalents) as lying far apart, and so
their natural topology is not that of the real numbers; in fact it is that of
the k-adic numbers which is a direct product of cyclic spaces. Near(k-adic)
seems to be near(real) but not necessarily the reverse, which relates the two
topologies to an extent. This discrepancy has caused much anguish, and seems to
be the historical reason for defining dynamical sustems in a certain way, and
not as sofic systems, which is the more inclusive concept.
Intuitively this topology regards configurations as being closer, the further
along their central segments agree; theoretically it makes the shift operation
continuous and the cellular automata become the manifestations of a continuous
map.
n another direction, Peter Grassberger has studied statistical properties of
the resulting "plaid diagrams" as typified by the following references:
Peter Grassberger, ``Long-Range Effects in an Elementary Cellular
Automaton,'' Journal of Statistical Physics45 27-39 (1986).
J. M. Greenberg and S. P. Hastings, ``Spatial patterns for discrete models of
diffusion in excitable media,'' SIAM Journal on Applied Mathematics34 515-523 (1978).
Gutowitz, Knight, Victor, "Local Structure Theory for CA", Physica D, volume
28, pgs. 18-48 (1987)
These diagrams can be generated using H. McIntosh's LCAU programs.
S. Amoroso and Y. N. Patt. Decision procedures for surjectivity and
injectivity of parallel maps for tesselation structures. Journal of
Computer and Systems Sciences, 6:448-464, 1972.
R. C. Backhouse and B. A. Carré. Regular algebra applied to path-finding
problems. Journal of the Institute for Mathematics and its
Applications, 15:161-186, 1975.
Robert Cori, Yves Metivier, and Wieslaw Zielonka. Asynchronous mappings
and asynchronous cellular automata. Information and computation,
106(2):159, October 1993.
Rajarshi Das, James P. Crutchfield, Melanie Mitchell, and James E. Hanson.
Evolving globally synchronized cellular automata. Technical report, Santa Fe
Institute Working Paper 95-01-005, 1995.
G. Bard Ermentrout and Leah Edelstein-Keshet. Cellular automata approaches
to biological modeling. Journal of Theoretical Biology, 160:97-133,
January 1993.
H.A. Gutowitz and Chris Langton. Mean field theory of the edge of chaos.
In F. Moran, A. Moreno, J.J. Merelo, and P. Chacon, editors, Advances in
Artificial Life: Proceedings of the Third European Conference on Artifical
Life, number 929 in Lecture Notes In Artificial Intelligence. Springer,
1995.
A. Hemmerling. On the computational equivalence of synchronous and
asynchronous cellular spaces. Elektronische Informationsverarbeitung und
Kybernetik, (now J. Inf. Process. Cybern. EIK), 18:423-434, 1982.
B. A. Huberman and N. Glance. Evolutionary games and computer simulations.
Proceedings of the National Academy of Sciences, USA, 90:7716-7718,
August 1993.
E. F. Moore. Machine models of self-reproduction. In A. W. Burks, editor,
Essays on Cellular Automata, pages 187-203. University of Illinois
Press, 1970. Moore's proof of the existence of ``Garden of Eden''
configurations in cellular automata: configurations which cannot occur under
the action of a specific CA rule. Moore also provides a way around Rosen's
paradox [].
Tadakazu Sato and Namio Honda. Certain relations between properties of
maps of tesselation automata. Journal of System and Computer
Sciences, 15:121-145, 1977.
M. Sipper. Quasi-uniform computation-universal cellular automata. In
ECAL95: 3rd European Conference on Artificial Life, Granada, Spain,
June 1995. Springer-Verlag.
Tommaso Toffoli. Computation and construction universality of reversible
cellular automata. Journal of Computer and Systems Sciences,
15:213-231, 1977.
S. Wolfram. Statistical mechanics of cellular automata. Reviews of
Modern Physics, 55:601-644, 1983. Important paper largely
responsible for the resurgence of interest in cellular automata.
S. Wolfram. Cellular automata as models of complexity. Nature,
311(4):419-424, 1984. A well written account of the manner in which
complex dynamics can emerge from simple components.
S. Wolfram, editor. Theory and Applications of Cellular Automata.
World Scientific, Singapore, 1986. Collection of papers on CA's.
Contains an extensive bibliography.
Yaku. Surjectivity of nondeterministic parallel maps induced by
nondeterministic cellular automata. Journal of Computer and Systems
Sciences, 12, 1976.
which
includes all of the partial recursive functions of one argument over N. A
programming system 
such
that 
for all i and x is itself a partial recursive function ; that is
if the system has a universal partial recursive function. A universal
programming system 
for all i and j.
on the
input x computes 
if
would
be represented as:
states per cell. Most cells are in the state i,0 for some
.
The cell where the ``head'' resides is in the state i,j for some
.
The update rule is for each cell to stay the same unless the
cell is where the ``head'' is or is a cell that the ``head''
is about to move into.
possible values so at SOME point the list must have a duplicate, i.e.,
if 
parameter of Langton, more general versions, which take into acount spatial
correlations, have also been developed.
implies 
. This, of course, is the general definition for functions. In the
case of CA a stronger result holds (reference?).
.
]
and strong [f(m) = m] equivalence under circumstances which look
suspiciously like requiring m and M to have eigenvalues which are either zeroes
or ones. If that were true, than the A and B matrices mentioned above would have
to share this property, and it would greatly simplify searching out reversible
pairs of cellular automata.