## Cellular Automata

*29 Dec 2012 15:10*

The chess-board is the world; the pieces are the phenomena of the universe; the rules of the game are what we call the laws of Nature.

---T. H. Huxley

Take a board, and divide it up into squares, like a chess-board or
checker-board. These are the cells. Each cell has one of a finite number of
distinct colors --- red and black, say, or (to be patriotic) red, white and
blue. (We don't allow continuous shading, and every cell has just one color.)
Now we come to the "automaton" part. Sitting somewhere to one side of the
board is a clock, and every time the clock ticks the colors of the cells
change. Each cell looks at the colors of the nearby cells, and its own color,
and then applies a definite rule, the *transition rule,* specified in
advance, to decide its color in the next clock-tick; and all the cells change
at the same time. (The rule can say "Stay the same.") Each cell is a sort of
very stupid computer --- in the jargon, a *finite-state automaton*
--- and so the whole board is called a *cellular automaton,* or CA. To
run it, you colors the cells in your favorite pattern, start the clock, and
stand back.

Now that (I hope) you have a concrete picture, I can get a bit more
technical, and more abstract. The cells don't have to be colored, of course;
all that's important is that each cell is in one of a finite number of states
at any given time. By custom they're written as the integers, starting from 0,
but any "finite alphabet" will do. Usually the number of states is small,
under ten, but in principle any finite number is OK. What counts as the
"nearby cells", the *neighborhood,* varies from automaton to automaton;
sometimes just the four cells on the principle directions, sometimes the corner
cells, sometimes a block or diamond of larger size; in principle any arbitrary
shape. You don't need to stick to a chess-board; you can use any pattern of cells
which will fill the plane (or "tessellate" it; an old name for cellular
automata is "tessellation structures"). And you don't have to stick to the
plane; any number of dimensions is allowed. (Well, any integer number of
dimensions. I doubt a fractal CA makes sense.) You do need to stick to
discrete time, to clock-ticks; but CA have cousins in which time is
continuous. There are various tricks for handling the edges of the board; the
one which has "all the advantages of theft over honest toil" is to assume an
infinite board.

One important use of CA is to mimic bits and pieces of the real world, or,
as they say in the trade, to model it. You'd
expect this to work well for things with lots of discrete little parts, and in
fact there are CA models for crystals and percolation and such forth. But
there are also CA for fluid flow (called *lattice gasses*), for
"reaction-diffusion" systems in chemistry and other sorts of pattern formation, for insect colonies, for
ecosystems, for the development of organisms, for traffic (some
even vaguely convincing), even for urban growth. There's a modest industry of
seeing which types of CA have various properties of interest to theoretical
physicists --- time-reversibility, various sorts of symmetry, etc. There's
even a current of thought pushing the idea that CA capture something really
fundamental about physics, that they are more physical than the differential
equations we have come to know and love these last three hundred years. I
can't say I buy this myself, but I also haven't examined it very deeply.

CA were not invented, however, to be realistic models of Nature. They
started with John von Neumann, who wanted to
study self-reproduction, and decided that the first thing to do was ignore
everything biologists had learned about the way actually existing organisms
reproduce themselves. This is known as *hubris,* and is especially
galling when it works. Von Neumann was able to prove that a certain CA can
have a "general constructive automaton," a configuration of states which can
construct almost any configuration of states. (Like most CA-wallahs, I used to
think that it was a "universal constructor" which could build absolutely
anything, but since writing the first version of this notebook I've been
privileged to hear Barry McMullin discourse on von Neumann's work to the SFI
journal club, and been set straight.) This was in the computational dark ages
--- see below --- so he did all this work with pencil and paper. He didn't
label his states with colors, but with little wiring-diagram-like icons, to
help show the function of each cell. The constructor is told what to build by
a "tape," a string of cells whose states the constructor read as instructions.
(Back in the dark ages, computers really were programmed by punched or magnetic
tape, and programming was called "taping.") If your initial set-up is a
constructor, and a tape which reads

- Build a general constructive automaton, according
*this*plan; - Copy this tape into the new constructor,

*voilà,*you have an automaton (constructor + tape) which will reproduce itself.

Von Neumann's design works, but it's *ugly.* You need twenty-nine
different states, a very complicated transition rule, and a huge constructor.
(Also time and patience; Dr. McMullin estimates six centuries, if each cycle of
the constructor can be run in only one second, which is a bit optimistic.)
Moreover the process doesn't look much like biological reproduction at all; to
begin with, DNA is (as Dawkins says) a recipe, not a
blue-print, and von Neumann definitely calls for blue-prints. And I don't have
to tell you that, in the physical world, general constructive automata are thin
on the ground --- for the moment, anyway.

Anyway, from von Neumann the torch was passed to his partner-in-crime, Stanislaw Ulam, and Arthur Burks and his "Logic of Computers" group at Michigan (Burks edited von Neumann's posthumous Theory of Self-Reproducing Automata, and one of the students in his group, E. F. Codd, was able to come up with a CA with universal construction using only eight states, and got a thesis out of it), and John Horton Conway, who devised the most notorious CA of all, the Game of Life.

Life has only two states, 1 and 0, standing for "living" and "dead", respectively. The transition rule is also simple. You look at all eight cells immediately around you. If less than two of your neighbors are alive, you die. If exactly two of your neighbors are live, you don't change. If exactly three of your neighbors are alive, you will be alive next turn, regardless of your current state. If four or more of your neighbors are alive, you are over-crowded and you die. --- Conway was thinking about colonial organisms, but it has to be one of the least convincing biological models ever. [Obviously, I wrote that before visiting the Santa Fe Institute.] It turns out that the number of interesting configurations you can make from these elements is immense: things which blink and oscillate; things which glide across the plane; things which eat the gliders; things which throw off the gliders like waste. (Enthusiasts have named all of these, and many more.) You can even prove that you can build a pukka universal computer out of these smaller configurations, and a self-reproducer, though I don't think anyone's had the patience to do it.

The growing interest in CA is, incidentally, a good example of what the late
Heinz Pagels meant when he talked about "the computer and the rise of the
sciences of complexity." It is extraordinarily difficult to predict, a priori,
how a CA will evolve from an arbitrary starting-point; usually the only way to
do it is to work the calculation through explicitly. You can try doing this by
hand --- Conway used to use Go boards, and Ulam something which, from the
photographs, resembled Jenga sticks, but the really interesting examples can
have more than a million cells, and even if they made boards that large, it
would take much too long. (Of course, if you can find more-or-less autonomous features,
like the blinkers and gliders in Life, that'd speed things up; this leads into
fascinating issues about causality and hierarchy
and emergence and epistemology, which I
may be rash enough to elaborate on another time. Onwards.) Clearly, if you
want to study these things, you need something which will do lots of
calculations very rapidly, and will not get bored, i.e. a computer. Von
Neumann recognized this from the first, and predicted (correctly) that computer
simulations would come to be used in much the same way as experiments in
natural science: simulations suggest theories, which in turn suggest new
simulations to check them. (Since you can also produce actual
mathematical *proofs* about CA, but not,
*pace* Spinoza, about Nature, the analogy is not perfect.)

This sounds very well, but the reality was that in the '50s and '60s,
computers were rare, slow, expensive, and visually incompetent. To judge from
the early papers, finding a machine you could *interact* with was a
religious experience, and one didn't object to seeing merely the hinder parts
of Jehovah. (One of the first visual displays was a spare oscilloscope Ulam
attached to a machine named JOHNIAC. I've seen screen photos, and they're
appalling.) Even puny and blinkered boxes at the level of an Apple II were
immense steps forward, since they can evolve a decent-sized Game of Life at a
speed which does not require the patience of a Benedictine copyist, and in fact
ever since Martin Gardner publicized Life in Scientific American,
a significant fraction of the world's computing power has been devoted to the
game. --- Of course, you get even better results if you build your computer
with running CA in mind; and there are people at MIT, who seem to have the
patience of Benedictine copyists, who have been devoting the last few decades
to such "cellular automata machines."

I'm interested in them for two big reasons:

- My graduate advisers studied them. (See, I conceal nothing from you.)
- They're a good place to study self-organization. They are simple, the mechanisms at work are completely known, and they can do just about anything, without any over-all guidance or intelligence.

Miraculous results have been achieved

through the simplest means:

a bottle, a prism, a lens, a fragment of paper, an apple,

and the august, etiolate skull of a sheep

high on a summer hill.

Still, I wouldn't turn up my nose at building a better screen-saver (or a better parallel computer).

*See also:*
Complexity;
Dynamics;
Math I ought to learn;
Pattern formation;
Random fields;
Self-organization;
Statistical mechanics;
Turbulence.

- Recommended, less technical:
- Daniel Dennett, "Real Patterns" in Brainchildren: Essays on Designing Minds [Using cellular automata to explicate the nature of patterns, emergent properties, and a great deal else besides. See my review of the book]
- Greg Egan, Permutation City. [This is the only science fiction I've read featuring cellular automata in any serious way. (Peter da Silva tells me that an early Piers Anthony novel makes heavy use of Life.) Recommending it on such grounds is a bit like recommending The Heart of Darkness just because it has Belgian characters, but this treatment of CA in fiction isn't likely to be surpassed any time soon. Review: Simulated Leibniz]
- David Griffeath, Primordial Soup Kitchen. [Intuitive explanations of the math, and really pretty pictures.]
- Steven Levy, Artificial Life, [Some interesting material on the history of CA. Unreliable on subjects like entropy and dissipative structures.]
- William Poundstone, Recursive Universe: Cosmic Complexity and the Limits of Scientific Knowledge, [An excellent popular book, partly about CA, partly about physics and complexity and philosophy of science in general; I first read it when I was twelve, and on re-reading find my memory has not improved it.]

- Recommended, more technical, general:
- Arxiv.org: nlin.CG [Online archive for papers on cellular automata and lattice gases; see also cond-mat and math.DS (dynamical systems).]
- Nino Boccara, Modeling Complex Systems [Review: How to Do It]
- Arthur W. Burks (ed.) of two fundamental books,
- John von Neumann, Theory of Self-Reproducing Automata [Not quite complete when von Neumann died of cancer.]
- Essays on Cellular Automata [Contributors include Ulam and John Holland. One of my more prized possessions.]

- J. Doyne Farmer, Tommasso Toffoli and Stephen Wolfram (eds.), Cellular Automata [1983 conference at Los Alamos, published as a book by Elsevier, and as a special issue of Physica D, vol. 10, nos. 1--2]
- Harold Gutowitz (ed.)
- The Cellular Automata FAQ
- Cellular Automata: Theory and Experiment =
Physica D
**45**

- Andrew Ilachinski, Cellular Automata: A Discrete Universe [Review by yours truly and Cris Moore]
- Paul Manneville, Nino Boccara, Gérard Y. Vichniac and R. Bidaux (eds.), Cellular Automata and Modeling of Complex Systems
- Norman Margolus and the Information Mechanics group at MIT (the aforementioned Benedictines). [Norm is probably one of only two persons in the world who fully understand the CAM, and was kind enough to teach me a bit about how to use it (also kind enough to pay for my dinner a few nights, at Santa Fe prices, when I was a penniless graduate student). The book he wrote with Tommaso Toffoli (the other person to full understand the CAM), Cellular Automata Machines, is quite good, especially on CA as physical modeling tools, something I've not really talked about, but the machine it describes is the CAM 6, and the current model, the CAM 8, has a horribly different and really very bizarre architecture, and, like its predecessor, is programmed in Forth. (Norm tells me that the next CAM, now being designed, will programmed in that best of all languages, Lisp.) The latest version of the Gospel according to Norm, to which I subscribe on alternate days, is Crystalline Computation, in A. J. G. Hey (ed.), Feynman and Computation.]
- The Santa Fe Institute's Evolving Cellular Automata Project and Computational Mechanics Group do some fascinating work on CA. It's OK for me to say that since I no longer work with them.

- Recommended, more technical, applications to modeling real stuff:
- Bruce Boghosian's
homepage will do as a proxy for his group at Boston University, which does
excellent work using CA as models for pattern formation in fluids.
- Maziar Nekovee, Peter V. Coveney, Hudong Chen and Bruce M. Boghosian, "A Lattice-Boltzmann Model for Interacting Amphiphilic Fluids," cond-mat/0006319
- B. M. Boghosian, J. Yepez, Peter V. Coveney and A. J. Wagner, "Entropic Lattice Boltzmann Methods," cond-mat/0005260
- Peter V. Coveney, Andrew N. Emerton and Bruce M. Boghosian, "Simulation of Self-Reproducing Micelles using a Lattice-Gas Automaton," cond-mat/9709183

- Raissa
M. D'Souza and Norman H. Margolus, "A Thermodynamically Reversible
Generalization of Diffusion Limited Aggregation," cond-mat/9810258 =
Physical Review E
**60**(1999): 264--274 - Rick Durrett [Durrett also does some quite theoretical probabilistic math, but most of his on-line papers here are related to using stochastic spatial systems, including cellulat automata, as ecological or evolutionary models]
- Martin Nilsson and Steen Rasmussen, "Cellular Automata for
Simulating Molecular Self-Assembly," Discrete Mathematics and Theoretical
Computer Science
**AB(DMCS)**(2003): 31--42 [Should be online at the journal web-site] - Janko Gravner and David Griffeath, Snowfakes [Models of snow-crystal formation]
- Daniel H. Rothman and Stéphane Zaleski, Lattice-Gas Cellular Automata: Simple Models of Complex Hydrodynamics [Good textbook on lattice gases; fortunate, since it seems to be the only textbook on lattice gases. Review]
- Thimo Rohlf and Stefan Bornholdt
- "Self-organized pattern formation and noise-induced control from particle computation", cond-mat/0312366 [Short version]
- "Morphogenesis by coupled regulatory networks", q-bio.MN/0401024 [Long version]

- Mark Smith, Cellular Automata Methods in Mathematical Physics [MIT Laboratory for Computer Science Technical Report 615]

- Recommended, more technical, pure theory, abstract models, etc.:
- Remo Badii and Antonio Politi
- Complexity: Hierarchical Structures and Scaling in Physics [Review]
- "Thermodynamics and Complexity of Cellular Automata", Physical Review Letters
**78**(1997): 444--447

- John Baez and James
Gilliam, "An Algebraic Approach to Discrete Mechanics," Letters in
Mathematical Physics
**31**(1994), 205--212 [Online in Postscript. To quote from This Week's Finds in Mathematical Physics**107**: "Here the idea was to set up as much as possible of the machinery of classical mechanics in a purely discrete context, where time proceeds in integer steps and the space of states is also discrete. The most famous examples of this `discrete mechanics' are cellular automata, which are the discrete analogs of classical field theories, but there are also simpler systems more reminiscent of elementary classical mechanics, like a particle moving on a line --- where in this case the 'line' is the integers rather than the real numbers. It turns out that with a little skullduggery one can apply the techniques of calculus to some of these situations, and do all sorts of stuff like prove a discrete version of Noether's theorem --- the famous theorem which gives conserved quantities from symmetries." This is impressive and interesting, but not, yet, of much practical use. In particular, they can only get conserved quantities from symmetries of a Lagrangian, but many CA don't have one...] - F. Bagnoli, R. Recthman and S. Ruffo, "Damage Spreading and
Lyapunov Exponents in Cellular Automata", Physics Letters
A
**172**(1992): 34--38 = cond-mat/9811159 - Kellie Michele Evans, "Larger than Life: threshold-range scaling of
Life's coherent structures," Physica
D
**183**(2003): 45--67 - Nazim A. Fates and Michel Morvan, "An Experimental Study of Robustness to Asynchronism for Elementary Cellular Automata", nlin.CG/0402016
- Robert Fisch, Janko Gravner and David Griffeath
- Lawrence Gray and David Griffeath, "The Ergodic Theory of
Traffic Jams", Journal of Statistical Physics
**105**(2001): 413--452 [paper + simulations] - J. Greenberg and S. Hastings, "Spatial Patterns for Discrete Models
of Diffusion in Excitable Media", SIAM Journal on Applied
Mathematics
**34**(1978): 515--523 [JSTOR] - David Griffeath and Cristopher Moore (eds.), New Constructions in Cellular Automata
- Torbjorn Helvik, Kristian Lindgren and Mats G. Nordahl, "Continity
of Information Transport in Surjective Cellular Automata",
Communications in
Mathematical Physics
**272**(2007): 53-74 [thanks to Mats for a preprint] - Navot Israeli and Nigel Goldenfeld, "On computational irreducibility and the predictability of complex physical systems", nlin.CG/0309047 [Establishing that many putatively complex and computationally irreducible CA can nonetheless be efficiently predicted, provided one merely asks for predictions of coarse-grained, large-scale properties. In particular, while Rule 110 is computationally universal, it can be so predicted. This ought to be obvious (as a general point, not about 110 in particular), but it's nice to have it demonstrated conclusively.]
- Cris Moore
- M. A. Shereshevsky, "Lyapunov Exponents for One-Dimensional
Cellular Automata", Journal of Nonlinear
Science
**2**(1992): 1--8 - Pierre Tissuer, "Cellular Automata and Lyapunov Exponents",
Nonlinearity
**13**(2000): 1547--1560 = math.DS/0312136 - Stephen Wolfram, Cellular Automata and Complexity [Useful collection of Wolfram's papers on CA. (Co-authors are listed in the smallest typeface legible without a magnifying glass.) He couldn't sell it, but he could give it away via comp.theory.cell-automata, which is where I got my copy. In fact, as of April 1997, the papers are available on-line. This does not mention Wolfram's patent on lattice gases.]
- Andrew Wuensche and Mike Lesser, The Global Dynamics of Cellular Automata: An Atlas of Basin of Attraction Fields of One-Dimensional Cellular Automata [Cf. Wuensche's Discrete Dynamics Lab program]

- Dis-recommended
- Stephen Wolfram, A New Kind of Science [Review: A Rare Blend of Monster Raving Egomania and Utter Batshit Insanity]

- Modesty forbids me to recommend:
- Wim Hordijk, CRS, and James P. Crutchfield, "Upper Bound on the Products of Particle Interactions in Cellular Automata," nlin.CG/0008038 [This should be called Hordijk's Rule.]
- CRS, Causal Architecture, Complexity and Self-Organization in Time Series, Transducers and Cellular Automata [Ph.D. thesis, UW-Madison, 2001.]
- CRS, "Optimal Nonlinear Prediction of Random Fields on Networks," math.PR/0305160 [Including CA as a special case]
- CRS, Robert Haslinger, Jean-Baptiste
Rouquier, Kristina Lisa
Klinkner and Cristopher Moore,
"Automatic Filters for the Detection of Coherent Structure in Spatiotemporal
Systems", Physical Review E
**73**(2006): 036104 = nlin.CG/0508001 - CRS, Kristina Lisa
Shalizi and Robert Haslinger, "Quantifying Self-Organization with Optimal
Predictors", Physical Review Letters
**93**(2004): 118701 = nlin.AO/0409024

- To read [with thanks to Luke Wagner for recommending manylattice
gas/lattice Boltzmann items]:
- Andrew Adamatzky, Identification of Cellular Automata
- Mark S. Alber, Yi Jiang and Maria A. Kiskowski, "Lattice gas cellular automata model for rippling and aggregation in myxobacteria", q-bio/0401014
- A. P. F. Atman, R. Dickman, J. G. Moreira, "Phase diagram of a probabilistic cellular automaton with three-site interactions," cond-mat/0210036
- Franco Bagnoli, "Cellular Automata", cond-mat/9810012 [introductory lecture notes]
- Franco Bagnoli, Andrea Guazzini, Emanuele Massaro, "Community-detection cellular automata with local and long-range connectivity", arxiv:1206.2262
- Franco Bagnoli and Raul Rechtman, "Thermodynamic
entropy and chaos in a discrete hydrodynamical
system", Physical Review E
**79**(2009): 041115 ["thermodynamic entropy density is proportional to the largest Lyapunov exponent of a discrete hydrodynamical systems, a deterministic two-dimensional lattice gas automaton"] - O. Baran, C. C. Wan and R. Harris, "Generalized Thermal Lattice Gases," comp-gas/9805001
- F. Barra and P. Gaspard, "Classical Dynamics on Graphs," nlin.CD/0011045
- L. Bertini, A. De Sole, D. Gabrielli, G. Jona-Lasinio, C. Landim, "Large deviation approach to non equilibrium processes in stochastic lattice gases", arxiv:math/0602557
- Bruce M. Boghosian and Washington Taylor, "Correlations and Renormalization in Lattice Gases," nlin.CG/9403003
- Laurent Boyer, Guillaume Theyssier, "On Local Symmetries And Universality In Cellular Automata", 26th International Symposium on Theoretical Aspects of Computer Science [STACS 2009], pp. 195--206arxiv:0902.1253
- Gianluca Caterina and Bruce Boghosian, "A "No-Go" Theorem for the Existence of an Action Principle for Discrete Invertible Dynamical Systems", nlin.CG/0611058 ["the problem of the existence of a least-action principle for invertible, second-order dynamical systems, discrete in time and space. ... [W]hen the configuration space is finite, a least-action principle does not exist... We dichotomize ...infinite configuration spaces into those of finite type for which this theorem continues to hold, and those ... for which [there is] a least-action principle. We also show how to recover an action by restriction of the phase space of certain second-order discrete dynamical systems." Sounds cool, but surprises me.]
- Julien Cervelle, Enrico Formenti, Pierre Guillon, "Sofic Trace of a Cellular Automaton", math.DS/0703241 [When can the sequence of states at a particular site in a 1D cellular automaton give us a sofic shift, in the sense of symbolic dynamics?]
- Philippe Chassaing, Jean Mairesse, "A non-ergodic PCA with a unique invariant measure", arxiv:1009.0143 [Here "PCA"="probabilistic cellular automaton"]
- Bastien Chopard and Michel Droz, Cellular Automata Modeling of Physical Systems
- Debashish Chowdhury and G. Vishwesha, "Cellular-automata models of ant-trail and vehicular traffic: similarities and differences," cond-mat/0201207
- Mauro Copelli and Osame Kinouchi, "Intensity Coding in Two-Dimensional Excitable Neural Networks", q-bio.NC/0409032 [Greenberg-Hastings cellular automata as a toy model of visual perception!]
- E. Edlund and Martin Nilsson Jacobi, "Renormalization of cellular
automata and
self-similarity", Journal
of Statistical Physics
**139**(2010): 972--984, arxiv:1108.3982 - A. Eizenberg and Y. Kifer
- "Large Deviations for Probabilistic Cellular
Automata", Journal of Statistical Physics
**108**(2002): 1255--1280 - "Large Deviations for Probabilistic Cellular Automata
II", Journal of
Statistical Physics
**117**(2004): 845--889

- "Large Deviations for Probabilistic Cellular
Automata", Journal of Statistical Physics
- Nazim Fates, "Directed percolation in asynchronous elementary cellular automata: a detailed study", nlin.CG/0703044
- U. Frisch, D. d'Humiéres, B. Hasslacher, P. Lallemand,
Y. Pomeau, J.-P. Rivet, Complex Systems
**1**(1987): 649 - Henryk Fuks, "Probabilistic cellular automata with conserved quantities," nlin/0305051
- Henryk Fuks and Nino Boccara, "Convergence to equilibrium in a class of interacting particle systems evolving in discrete time," nlin.CG/0101037
- Peter Gács
- "Reliable Cellular Automata with Self-Organization," math.PR/0003117
- "A Toom rule that increases the thickness of sets," math-ph/0102009

- Jason A. C. Gallas and Hans J. Errmann, "Spontaneous Emergence of Spatio-Temporal Order in Class 4 Automata", cond-mat/0505011 [OK, clearly I have to read this, because it's gotten in to a reasonably journal, but from the abstract sounds completely unsurprising, so I'm missing something]
- Eric Goles Servet Martinez, Neural and Automata Networks: Dynamical Behavior and Applications
- Janko Gravner, Craig A. Tracy and Harold Widom, "A growth model in a random environment," math.PR/0011150
- Geoffrey Grimmett, Probability on Graphs: Random Processes on Graphs and Lattices [blurb]
- A. Guionnet and B. Zegarlinski, Lectures on Logarithmic Sobolev Inequalities [120 pp. PDF]
- Brian P. Hoke, Cellular Automata and Art
- J. O. Indekeu and C. V. Giuraniuc, "Cellular automaton for
bacterial towers", Physica
A
**336**(2004): 14--26 - Navot Israeli and Nigel Goldenfeld, "Coarse-graining of cellular automata, emergence, and the predictability of complex systems", nlin.CG/0508033
- Wolfram Just, "Phase transitions in coupled map lattices and
in associated probabilistic cellular automata",
Physical Review
E
**74**(2006): 046209 - L. Kadanoff, G. McNamara, and G. Zanetti, Physical Review
A
**40**4527 (1989) - Jarkko Kari, "Theory of cellular automata: A survey", Theoretical Computer
Science
**334**(2005): 3--33 ["This article surveys some theoretical aspects of cellular automata .... We discuss classical and new results on reversibility, conservation laws, limit sets, decidability questions, universality and topological dynamics of CA. The selection of topics is by no means comprehensive and reflects the research interests of the author. The main goal is to provide a tutorial of CA theory to researchers in other branches of natural computing, to give a compact collection of known results with references to their proofs, and to suggest some open problems."] - Thomas M. Liggett
- Interacting Particle Systems [1st ed.]
- Stochastic Interacting Systems: Contact, Voter, and Exclusion Processes [2nd ed.]

- P.-Y. Louis, "Increasing coupling of probabilistic cellular
automata", Statistics and
Probability Letters
**74**(2005): 1--13 - Carsten Marr, Marc-Thorsten Huett, "Outer-totalistic cellular automata on graphs", Physics Letters A
**373**(2008): 546--549, arxiv:0812.2408 - Bruno Martin
- "Damage spreading and $\mu$-sensitivity on cellular
automata", Ergodic
Theory and Dynamical Systems
**27**(2007): 545--565 ["We show relations between new notions on cellular automata based on probabilistic dynamics: almost everywhere sensitivity to initial conditions for Besicovitch pseudo-distance, damage spreading (which measures the information (or damage) propagation) and the destruction of the initial configuration information. Through natural examples, we illustrated the relations between these formal definitions"] - "Apparent entropy of cellular automata", Complex
Systems
**11**(1997) [Abstract: "We introduce the notion of apparent entropy on cellular automata that points out how complex some configurations of the space-time diagram may appear to the human eye. We then study, theoretically if possibly, but mainly experimntally through natural examples, the relations between this notion, Wolfram's intuition, and almost-everywhere sensitivity to initial conditions"]

- "Damage spreading and $\mu$-sensitivity on cellular
automata", Ergodic
Theory and Dynamical Systems
- David Meyers
- "From Quantum Cellular Automata to Quantum Lattice Gases," quant-ph/9604003
- "Unitarity in One Dimensional Nonlinear Quantum Cellular Automata," quant-ph/9605023

- Tomohiro Miura, Tai Tanaka, Yoshikazu Suemitsu and Shigetoshi Nara,
"Complete and compressive description of motion pictures by means of
two-dimensional cellular automata", Physics Letters
A
**346**(2005): 296--304 [this sounds interesting, based on the abstract, but (a) have they accounted for the cost of encoding their spatially-varying ruleset? and (b) why not publish in an information theory journal?] - Marcus Pivato
- "Algebraic invariants for crystallographic defects in cellular automata", math.DS/0507167
- "Cellular Automata vs. Quasistrumian Shifts", Ergodic
Theory and Dynamical Systems
**forthcoming**(2005) = math.DS/0503502 - "Conservation Laws in Cellular Automata," math.DS/0111014
- "Defect Particle Kinematics in One-Dimensional Cellular Automata", math.DS/0506417
- "Linear cellular automata, asymptotic randomization, and entropy," math.DS/0210241
- "Nonabelian Multiplicative Cellular Automata," math.DS/0108084
- "RealLife: the continuum limit of Larger Than Life cellular automata", math.DS/0503504
- "Spectral domain boundaries in cellular automata", math.DS/0507091

- Marcus Pivato and Reem Yassawi
- "Limit Measures for Affine Cellular Automata," parts I, math.DS/0108082, and II, math.DS/0108083
- "Asymptotic behaviour of measures with long range correlations under the action of cellular automata," math.DS/0210232

- Wolfgang Radax, Bernhard Rengs, "Timing matters: Lessons From The CA Literature On Updating", arxiv:1008.0941
- Jean-Baptiste Rouquier and Michel Morvan, "Coalescing Cellular Automata", nlin.CG/0610009
- Andreas Schadschneider and Michael Schreckenberg, "Comment on `Garden of Eden states in traffic model revisited'," cond-mat/0201214
- Frank Schweitzer, Laxmidhar Behera, "Nonlinear Voter Models: The Transition from Invasion to Coexistence", European Physical Journal B
**67**(2009): 301--318, arxiv:0307742 - Angela B. Shiflet and George W. Shiflet, Introduction to Computational Science: Modeling and Simulation for the Sciences [Sounds like it includes a lot on cellular automata, not sure how advanced. Blurb, sample text]
- Amer Shreim, Peter Grassberger, Walter Nadler, Björn Samuelsson, and Joshua E. S. Socolar, "Network Analysis of the State Space of Discrete Dynamical Systems", cond-mat/0610447
- Matthew J. Simpson, Alistair Merrifield, Kerry A. Landman, and
Barry D. Hughes, "Simulating invasion with cellular automata: Connecting
cell-scale and population-scale
properties", Physical Review
E
**76**(2007): 021918 - Quentin F. Stout, "Using Clerks in Parallel Processing",
pp. 272--279 in Proceedings of the 23rd IEEE Symposium on Foundations of
Computer Science (1982) [
*Abstract*: "Some models of parallel computers consist of copies of a single finite state automaton connected together in a regular fashion. In such computers a self-organizing structure called*clerks*can be useful, enabling one to simulate a more powerful computer for which optimal algorithms are easier to design. The computation proceeds by having the cellular automata organize themselves into clerks, and then a stepwise simulation of the more powerful computer is performed. For a system of n automata, each clerk contains \Theta(log n) automata, so first they need to determine log(n), despite the fact that no single automata can count higher than a fixed number." Link] - Sauro Succi, Iliya V. Karlin and Hudong Chen, "Role of the H theorem in lattice Boltzmann hydrodynamic simulations," cond-mat/0205639
- Veronique Terrier, "Two-dimensional cellular automata and their
neighbrohoods", Theoretical Computer
Science
**312**(2004): 203--222 ["We investigate how the choice of the neighborhood can influence the computation ability of two-dimensional cellular automata. We present also a strict inclusion between low and high complexity classes of two-dimensional cellular automata."] - Tommaso Toffoli, Silvio Capobianco, Patrizia Mentrasti, "When--and how--can a cellular automaton be rewritten as a lattice gas?", 0709.1173
- Andre Toom, "Law of Large Numbers for Non-Local
Functions of Probabilistic Cellular Automata", Journal of Statistical Physics
**133**(2008): 883--897 - Stanislaw Ulam, Adventures of a Mathematician
- Dejan Vinkovic and Alan Kirman, "A Physical Analogue of the
Schelling Model", Proceedings
of the National Academy of Sciences
**103**(2006): 19261--19265 - Voorhees, One-Dimensional Cellular Automata
- Alexander J. Wagner, "An H-Theorem for the Lattice Boltzmann Approach to Hydrodynamics," cond-mat/9808052
- L. Wagner, "Dependence of drag on a Galilean invariance-breaking
parameter in lattice-Boltzmann flow simulations," Physical Review
E
**49**2115 (1994) - Wen-an Yong and Li-Shi Luo, "Nonexistence of H Theorem for Some
Lattice Boltzmann
Models", Journal of
Statistical Physics
**121**(2005): 91--103 - Huidan Yu, Sharath S. Girimaji and Li-Shi Luo, "Lattice Boltzmann
simulations of decaying homogeneous isotropic turbulence", Physical Review
E
**71**(2005): 016708 - Y. Zhao, S. A. Billings
and Alexander
F. Routh, "Identification of Excitable Media Using Cellular Automata
Models", International Journal
of Bifurcation and Chaos
**17**(2007): 153--168