Cellular Automata FAQ


[Non-Java version]

Generalites

Collapse all tree nodesExpand all tree nodes
Expand this node
Expand/collapse
Expand this node
What are Cellular Automata (CA)?
Contributions by: Lyman Hurd <hurd@math.gatech.edu>

Here is one physicist's view of the relevant definitions:

A cellular automaton is a discrete dynamical system. Space, time, and the states of the system are discrete. Each point in a regular spatial lattice, called a cell, can have any one of a finite number of states. The states of the cells in the lattice are updated according to a local rule. That is, the state of a cell at a given time depends only on its own state one time step previously, and the states of its nearby neighbors at the previous time step. All cells on the lattice are updated synchronously. Thus the state of the entire lattice advances in discrete time steps.

Here is one mathematician's view of the relevant definitions:

Conventions d=dimension, k=states per site, r=radius (all explained below).

For simplicity, assume d=1 for the moment.

A d-dimensional cellular automaton takes as its underlying space the lattice (Z=integers, infinite in both positive and negative directions) where S is a finite set of k elements. The dynamics are determined by a global function

whose dynamics are determined ``locally'' as defined below.

A ``local (or neighborhood) function'' f is defined on a finite region

The all-important property of cellular automata, is that this function is determined by a finite lookup table. Both the domain and range of f are finite.

The global function F arises from f by defining:

A concrete example with k=2,r=1 would take a doubly infinite string of zeroes and ones to a new string at which each site is replaced by the logical and of its two neighbors (Wolfram's elementary rule 90).

Some relevant facts from a topological standpoint are:

  1. The base space is compact and the global function F is continuous.

    To insert an editorial comment, this makes CA an ideal meeting point between continuous dynamics and complexity theory, since they are discretely defined but exhibit continuous dynamics.

  2. The map F commutes with the shift operator which takes to .

In fact cellular automata are characterized completely by properties 1) and 2) (Hedlund).

The transition to more dimensions is straightforward. The only difference is that the global function F is defined over (functions from a d-dimensional lattice to S) and the local function f is determined by enumerating the image of all patches of size .

For an introduction to CA, some of the more well-known references are:

[Wol86] [TM87] [Gut91] [Wol94]

Expand this node
Expand/collapse
Expand this node
How do I contribute bibliographic material to the FAQ?
Currently, bibliographic submissions are not being accepted.
Expand this node
Expand/collapse
Expand this node
Where are cellular automata discussed?
The Usenet newsgroup comp.theory.cell-automata is a good place for discussing cellular automata.

Archives of this group are available on Google.

Archives from before 1995 are available here.

Expand this node
Expand/collapse
Expand this node
What should I work on in CA for my Ph.D. thesis?

Contributions by:

  • Bruce Boghosian <bruceb@conx.bu.edu>
  • Stephen Wolfram <sw@wri.com>
  • Harold McIntosh <mcintosh@servidor.dgsca.unam.mx>

This question sparked an interesting discussion on the CA list a while back. Some, noting the difficult job market for scientists, and the ill-repute of CA in some circles, replied, "Nothing, if you want to get a job." Some more upbeat and constructive remarks follow.

Boghosian: Lest today's funding realities make us too somber and cynical, I offer some words from George Bernard Shaw:

"The reasonable man adapts himself to the world; the unreasonable man persists to adapt the world to himself. Therefore, all progress depends on the unreasonable."

I certainly agree that grad students should be well informed about their options if they elect to pursue a dissertation in a nontraditional field such as cellular automata. I would, however, strongly disagree with the allegation that nontraditional research tends to be of lower quality.

For every one "free thinker" that succeeds, there may be fifty that do not and retreat to the mainstream, but there are many examples of key advances in science that would simply never have happened if those fifty people had not been willing to stick their necks out a bit and try something new.

Wolfram:

Here is a list of questions about cellular automata that I discussed in my 1984 paper: "Twenty Problems in the Theory of Cellular Automata", published in the proceedings of the 59th Nobel Symposium, and reprinted in my book: "Cellular Automata and Complexity: Collected Papers" (Addison-Wesley, 1994):

1. What overall classification of cellular automata can be given?

2. What are the exact relations between entropies and Lyapunov exponents for cellular automata?

3. What is the analog of geometry for the configuration space of a cellular automaton?

4. What statistical quantities characterize cellular automaton behavior?

5. What invariants are there in cellular automaton evolution?

6. How does thermodynamics apply to cellular automata?

7. How is different behavior distributed in the space of cellular automaton rules?

8. What are the scaling properties of cellular automata?

9. What is the correspondence between cellular automata and continuous systems?

10. What is the correspondence between cellular automata and stochastic systems?

11. How are cellular automata affected by noise and other imperfections?

12. Is regular language complexity generically non-decreasing with time in one-dimensional cellular automata?

13. What limit sets can cellular automata produce?

14. What are the connections between the computational and statistical characteristics of cellular automata?

15. How random are the sequences generated by cellular automata?

16. How common are computational universality and undecidability in cellular automata?

17. What is the nature of the infinite size limit for cellular automata?

18. How common is computational irreducibility in cellular automata?

19. How common are computationally intractable problems about cellular automata?

20. What higher-level descriptions of information processing in cellular automata can be given?

Most of these questions have now received at least some attention, but still none can really be considered solved. My own research over the past several years would lead to me to formulate slightly different questions, but I think the ones above are nevertheless a useful starting point.

And if anyone manages to come up with a definitive solution to any of these questions, I can say that I at least will be very interested in hiring them!

- Stephen Wolfram

McIntosh: Possibly the field is less active than it used to be, something which can be judged by the volume of CA-Mail in comparison with past years. For one thing, lattice gasses have split off from cellular automata, and then the support for the kind of hydrodynamics which requires lattice gasses may have diminished. For another, the a-life group was created, carrying with it an activity which was related to cellular automata, although not strictly a part of it. And then there are neural networks, Petri nets, Lindenmayer systems, and so on. So there is much to choose from, in areas generally related to automata.

The topics which Howard Gutowitz covered in his own thesis have still not been exhausted; there was another similar thesis (published as Wilbur, Lippman, Sharma, "on the prediction of local patterns in cellular automata" in the same time frame of ten years ago), but things seem to have been left where they were back then.

To a certain extent, everyone managed to show that a sophisticated treatment was considerably harder (or at least computationally more involved) than the naive treatment. Gutowitz, Victor, and Knight also ventured to two dimensions, again finding that the problems there were harder, especially in dealing with Kolmogoroff's requirements for subdividing probabilities.

Now that time has elapsed, understanding has grown, machines are faster, and programs are better, there could be an opportunity to return to the topic - which consisted in getting good probability measures to describe automata and their evolution. How good? Studies on binary automata exist; would anything (like better statistics) be gained by working with more states? Is the Wolfram classification scheme adequate for these automata? Can we make do with mean field theory, especially by recognizing its limitations (avoid totalistic rules)?

And speaking of the avoidance of totalistic rules, is there a reason why someone should not concentrate on totalistic rules and try to derive their special characteristics? For starters, sums might be thought to obey a Gaussian distribution, but empirical evidence suggests a more nearly uniform distribution.

The (not now so recent) work of Chaté and Manneville opens up a whole new world of automata, both experimentally and theoretically. Phenomonologically they have something like semiconductors, wherein a small amount of impurities can substantially modify the overall evolution of an automaton. Someone who wanted a nice project could try to find out more about the kinds of automata exhibiting the effect, practical ways to manage the impurities, and above all try to find an adequate theory to describe them and predict their behavior.

The problem is that classical iteration theory just doesn't apply to this class of automata, but yet there is regularity to be seen at work. One loses the theorems about conservation of fixed points and counterimages of critical points, but surely there is something which could take their place for composite rather than iterated functions?

Even for classical automata like Life, there are practical and philosophical problems which could be approached by having available an adequate theory of composite functions. Questions of long term evolution - not hundreds or millions, but zillions, of generations - need an adequate theory of limits before speculations can be tested and made reliable. Will a Universal Life computer EVER evolve spontaneously, under any reasonable (or unreasonable) conditions?

This is probably way beyond the range of a Ph.D. thesis.

Even if the thesis project were not to explore new theories or new aspects of old theories, there is certainly a use for programs which will calculate answers to all the questions which can be asked about automata. This might result in a project more worthy of Computer Science than Mathematics. Of course it is true that several programs already exist; nevertheless computer technology keeps advancing, bringing with it the possibility of having better programs, or even just programs with better interactive potential. Or more widely available for different platforms (to use a buzz word).

Visual display keeps getting better and better, so effective presentation of three dimensional automata is more feasible than it used to be. Not only might this aid the seardh for three-dimensional Life, it is also the proper domain of the Chaté-Manneville automata. Not to mention carrying Belusov- Zhabotinsky reactions into three dimensions. Again this may be more of an engineering or computational thesis than one in physics or mathematics; well, the request was for topics, without specifying with which faculty or school.

A person seeking a thesis topic might do well to see what topics have proven successful in recent years, either to use them as a model or even to decide on what to avoid. Two more which come to mind were written by Lyman Hurd and Jarkko Kari, respectively. The former was concerned with the limit sets which could arise under long time evolution, mostly of one dimensional automata, and so related to the limiting evolution problem already mentioned.

The latter made a highly regarded analysis of decidability problems in two dimensions (and, by inference, beyond). This may or may not have exhausted the topic, but one thinks not.

Maybe some final words on the politics of thesis choice are in order. Obviously it would be prudent to take into account the interests of the faculty members of the Department in which one intends to write the thesis. A sympathetic advisor is evidently a considerable asset. On the other hand, it is one's own life and education which is at stake, not the professor's. There will be far fewer opportunities to study something in which one is particularly interested outside of the university environment than within it. Therefore the selection of a thesis topic ought to reflect one's own interests; it is alright to ask around for ideas or suggestions, but in the end it is the person who writes the thesis who is going to have to make the decisions as to what it will contain, what its orientation is to be and so on.

As far as the choice of a thesis topic affecting job opportunities, there is no doubt that there is going to be some correlation. Still, there is always the question of why one is studying in the first place? Is it to learn something about the world, or is it to get some preliminary job training? How many people have the opportunity (or the desire) to follow up their thesis work in later life?

Somehow, a thesis is supposed to culminate a program of graduate studies by demonstrating that its author has dominated several skills, such as making a sensible choice of level and theme, the ability to make a survey of the literature, the ability to write a scientific document with a certain minimum of literary merit, and, of course, to make an original contribution to the body of scientific knowledge.

A sensible employer will judge the degree to which these criteria have been met; offering employment in kind will probably seem less important than trying to judge whether the prospective employee is alert, intelligent, versatile, ... . If the original goal was to prepare for technical employment, there should be no conflict. Having grown fond of the thesis topic and wanting to specialize immediately in following it up, the recent graduate is likely going to have to be more aggressive and persistent. Does this come as a surprise?

See also:

Grad Student - a grad student's experiences.

Expand this node
Expand/collapse
Expand this node
What are some good general references for CA?
Contributions by:
  • Mark A Biggar <mab@dst17.wdl.loral.com>
  • John Baez <baez@guitar.ucr.edu>
  • Mark Randell <markar@psy.uwa.oz.au>

Description of Adamatzky's book
Description of Voohees' book
Expand this node
Expand/collapse
Expand this node
What is the Complex Systems Journal?
A journal devoted to the rapid publication of research on the science, mathematics, and engineering of systems with simple components but complex overall behavior.

Editor: Stephen Wolfram, Wolfram Research, Inc., and University of Illinois

Expand this node
Expand/collapse
Expand this node
What is the AMS classification for CA?

Contributions by: Mike Hurley mgh3@po.cwru.edu

68Q80 is Computer Science / Theory of computing / Tessellation automata, iterative arrays, cellular structures

58F 08 is Global analysis, analysis on manifolds / dynamical systems / point mapping properties; ...; dynamics of cellular automata.

Expand this node
Expand/collapse
Expand this node
References
Ada94
Andrew Adamatzky. Identification of Cellular Automata. Taylor and Francis, London, Bristol, 1994.

FTW84
J. D. Farmer, T. Toffoli, and S. Wolfram, editors. Cellular Automata: Proceedings of an Interdisciplinary Workshop at Los Alamos, New Mexico, March 7-11, 1983, Amsterdam, 1984. North-Holland.
A collection of papers on the theory and applications of cellular automata.

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

SZ90
R. Serra and G. Zanarini. Complex Systems and cognitive processes. Springer-Verlag, 1990. see Chapter 3.

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

WL92
Andrew Wuensche and Mike Lesser. The Global Dynamics of Cellular Automata, volume Reference Vol 1 of Santa Fe Institute Studies in the Sciences of Complexity. Addison-Wesley, 1992. IBSN 0-201-55740-1.

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

Wol94
Stephan Wolfram. Cellular Automata and Complexity: Collected Papers. Addison-Wesley, 1994. revision of [Wol86] Paperback: ISBN 0-201-62664-0, Hardcover: ISBN 0-201-62716-7.