Cellular Automata FAQ


[Non-Java version]

Properties

Collapse all tree nodesExpand all tree nodes
Expand this node
Expand/collapse
Expand this node
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.

References

[1] [MY78] [2] [Mar94] [3] [AI87]

Expand this node
Expand/collapse
Expand this node
Is self reproduction possible in a CA?

Contributions by:

<mlk@asu.edu> <morita@ke.sys.hiroshima-u.ac.jp> Moshe Sipper <moshes@math.tau.ac.il>

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

here.

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.

Expand this node
Expand/collapse
Expand this node
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.

Expand this node
Expand/collapse
Expand this node
Can flocking behavior be observed in CA?

Contributions by: Rudy Rucker <rucker@sjsumcs.SJSU.EDU> Craig Reynolds <craig@green.studio.sgi.com> Ric Colasanti <R.Colasanti@sheffield.ac.uk>

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.

The canonical flocking paper is [Rey87].

Expand this node
Expand/collapse
Expand this node
What is Computronium?
Contributions by:

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.

...and...

CAM-8

Expand this node
Expand/collapse
Expand this node
What are 'basins of attraction'?

Contributions by: Harold McIntosh <mcintosh@redvax1.dgsca.unam.mx>

References

[BC75]

[Jen88] [] [Li87] [Nas78] [McI91b] [McI91a] [Wol83] [Wol84b] [Wol84a] [Wol86] [Gut91b]

Expand this node
Expand/collapse
Expand this node
What is a Garden of Eden?
Contributions by:

Harold McIntosh <mcintosh@servidor.unam.mx>

"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.

Expand this node
Expand/collapse
Expand this node
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

References

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.

[DCMH95], [VT79], [Gol78], [Hem82], [Nak74], [T.E84], [CMZ93], [Zei82], [NM92], [HG93], [Oli94], [CAI87], []

See Scott Page <scotte@mrfloods.caltech.edu> for a draft ms. on incentive-based asynchronous updating in CA.

Expand this node
Expand/collapse
Expand this node
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.

Expand this node
Expand/collapse
Expand this node
Is there is universal 1D CA?

Is there is universal 1D CA?

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.

References

[Smi71] [LN90]

Expand this node
Expand/collapse
Expand this node
What about running a CA in reverse?

Contributions by: Lyman Hurd <hurd@math.gatech.edu>

The General Case

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:

  1. Is there a configuration which maps onto this configuration?
  2. 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.

Expand this node
Expand/collapse
Expand this node
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:

Expand this node
Expand/collapse
Expand this node
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.

Expand this node
Expand/collapse
Expand this node
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.

Expand this node
Expand/collapse
Expand this node
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.

References

[] [Wol83] [] [Gut91a] [McI90]

Expand this node
Expand/collapse
Expand this node
When is a CA injective, surjective?

Contributions by: Lyman Hurd <hurd@math.gatech.edu>

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).

Expand this node
Expand/collapse
Expand this node
Can one decide if a 2D rule is reversible/surjective?

Contributions by: Lyman Hurd <hurd@math.gatech.edu>

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.

Expand this node
Expand/collapse
Expand this node
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.

Expand this node
Expand/collapse
Expand this node
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 Theory 3 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 Society 25 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 Physics 45 27-39 (1986).

J. M. Greenberg and S. P. Hastings, ``Spatial patterns for discrete models of diffusion in excitable media,'' SIAM Journal on Applied Mathematics 34 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.

Expand this node
Expand/collapse
Expand this node
What about mixing CA rules?

What about mixing CA rules?

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
Expand this node
Expand/collapse
Expand this node
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.
Expand this node
Expand/collapse
Expand this node
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 Theory 3 320-375 (1969).
  • Roy Adler and Leopold Flatto, ``Geodesic Flows, Interval Maps, and Symbolic Dynamics,'' Bulletin of the American Mathematical Society 25 229-334 (1991).
  • Masakazu Nasu, "Textile Systems for Endomorphisms and Automorphisms of the Shift", to appear in Memoirs of A.M.S.

Expand this node
Expand/collapse
Expand this node
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

Voorhees

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.

McIntosh

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.

Expand this node
Expand/collapse
Expand this node
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 Physics 45 27-39 (1986).

J. M. Greenberg and S. P. Hastings, ``Spatial patterns for discrete models of diffusion in excitable media,'' SIAM Journal on Applied Mathematics 34 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.

Expand this node
Expand/collapse
Expand this node
References
AI87
J. Albert and K. Culik II. A simple universal cellular automaton and its one-way and totalistic version. Complex Systems, 1:1-16, 1987.

AP72
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.

BC75
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.

CAI87
K. Cheung, L. Atlas, and R. Marks II. Synchronous vs asynchronous behavior of hopfield's CAM neural net. Appl. Optics, 26:4808-13, 1987.

CM91
H. Chate and P. Maneville. Evidence of collective behavior in cellular automata. Europhysics Letters, 14:409-413, 1991.

CMZ93
Robert Cori, Yves Metivier, and Wieslaw Zielonka. Asynchronous mappings and asynchronous cellular automata. Information and computation, 106(2):159, October 1993.

CP74
Ethan M. Coven and Michael E. Paul. Endomorphisms of irreducible subshifts of finite type. Mathematical Systems Theory, 8:167-175, 1974.

CP75
Ethan M. Coven and Michael E. Paul. Sofic systems. Israel Journal of Mathematics, 20:165-177, 1975.

CP77
Ethan M. Coven and Michael E. Paul. Finite procedures for sofic systems. Monatshefte fuer Mathematik, 83:265-278, 1977.

DCMH95
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.

EEK93
G. Bard Ermentrout and Leah Edelstein-Keshet. Cellular automata approaches to biological modeling. Journal of Theoretical Biology, 160:97-133, January 1993.

FT82
Edward Fredkin and Tommaso Toffoli. Conservative logic. International Journal of Theoretical Physics, 21:219-253, 1982.

Gar83
Martin Gardner. Wheels, Life, and Other Mathematical Amusements. W. H. Freeman and Company, New York, 1983. ISBN 0-7167-1589-9.

GL95
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.

Gol78
U. Golze. (A-)synchronous (non-)deterministic cell spaces simulating each other. J. Computer and Systems Sciences, 17:176-193, 1978.

Gut91a
Howard Gutowitz, editor. Cellular Automata: Theory and Experiment, 1991. Published as Physica D45 (1990) Nos. 1-3, and as MIT press book.

Gut91b
Howard Gutowitz. Transients, cycles and complexity in cellular automata. Physical Review A, 44(12):7881-7884, December 1991.

Hem82
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.

HG93
B. A. Huberman and N. Glance. Evolutionary games and computer simulations. Proceedings of the National Academy of Sciences, USA, 90:7716-7718, August 1993.

Jen88
Erica Jen. Cylindrical cellular automata. Communications in Mathematical Physics, 118:569-590, 1988.

Li87
Wentian Li. Power spectra of regular languages and cellular automata. Complex Systems, 1:107-130, 1987.

LN90
Kristian Lindgren and Mats G. Nordahl. Universal computation in simple one-dimensional cellular automata. Complex Systems, 4(3):299-318, June 1990.

Mar94
B. Martin. A universal cellular automaton in quasi-linear time and its S-m-n form. Theoretical Computer Science, (123):199-237, 1994.

McI90
H. V. McIntosh. Wolfram's class IV automata and a good life. Physica D, 45:105, 1990.

McI91a
Harold V. McIntosh. Linear cellular automata via de bruijn diagrams. preprint, May 1991.

McI91b
Harold V. McIntosh. Reversible cellular automata. preprint, January 1991.

Moo70
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 [].

MY78
M Machtey and P. Young. An introduction to the general theory of algorithms. Elsevier North Holland, 1978.

Nak74
K. Nakamura. Asynchronous cellular automata and their computational ability. Systems, Computer, Control, 5:58-66, 1974.

Nas78
Masakazu Nasu. Local maps inducing surjective global maps of one dimensional tesselation automata. Mathematical Systems Theory, 11:327-351, 1978.

Nas82
Masakazu Nasu. Uniformly finite-to-one and onto extensions of homomorphisms between strongly connected graphs. Discrete Mathematics, 39:171-197, 1982.

NM92
Martin A. Nowak and Robert M. May. Evolutionary games and spatial chaos. Nature, 359:826-829, 1992.

Oli94
M. Oliphant. Evolving cooperation in the non-iterated prisoner's dilemma. In R Brooks and P. Maes, editors, Artificial Life IV. MIT Press, 1994.

Ped92
John Pedersen. Cellular automata as algebraic systems. Complex Systems, 6(3):237-250, June 1992.

Rey87
Craig Reynolds. Flocks, herds, and schools: A distributed behavioral model. Proceedings of ACM Computer Graphics, 21(4):25-33, July 1987.

Ric72
D. Richardson. Tesselations with local transformations. Journal of Computer and Systems Sciences, 5:373-388, 1972.

SH77
Tadakazu Sato and Namio Honda. Certain relations between properties of maps of tesselation automata. Journal of System and Computer Sciences, 15:121-145, 1977.

Sip95a
M. Sipper. Quasi-uniform computation-universal cellular automata. In ECAL95: 3rd European Conference on Artificial Life, Granada, Spain, June 1995. Springer-Verlag.

Sip95b
M. Sipper. Studying artificial life using a simple, general cellular model. Artificial Life Journal, 2(1), 1995. The MIT Press, Cambridge, MA.

Smi71
Smith. Cellular automata complexity trade-offs. Information and Computation (formerly Information and Control), 18, 1971.

T.E84
R. L. Buvel T.E. Ingerson. Structure in asynchronous cellular automata. Physica D, 1:59-68, 1984.

TM87
Tommaso Toffoli and Norman Margolus. Cellular Automata Machines. MIT Press, London, 1987.

Tof77
Tommaso Toffoli. Computation and construction universality of reversible cellular automata. Journal of Computer and Systems Sciences, 15:213-231, 1977.

VT79
R. Vollmar and B. G. Teubner. Algorithmen in Zellularautomaten. Stuttgart, 1979.

Wei73
Benjamin Weiss. Subshifts of finite type and sofic systems. Monatshefte fuer Mathematik, 77:462-474, 1973.

Wol83
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.

Wol84a
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.

Wol84b
Stephan Wolfram. Random sequence generation by cellular automata. Adv. Appl. Math, 7:123, 1984.

Wol86
S. Wolfram, editor. Theory and Applications of Cellular Automata. World Scientific, Singapore, 1986.
Collection of papers on CA's. Contains an extensive bibliography.

Yak76
Yaku. Surjectivity of nondeterministic parallel maps induced by nondeterministic cellular automata. Journal of Computer and Systems Sciences, 12, 1976.

Zei82
Bernard P. Zeigler. Discrete event models for cell space simulation. International Journal of Theoretical Physics, 21(6/7):573-588, 1982.