Notebooks

## 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

1. Build a general constructive automaton, according this plan;
2. Copy this tape into the new constructor,
then 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:

1. My graduate advisers studied them. (See, I conceal nothing from you.)
2. 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.
As the poet says,
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).

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.)
• 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
• "Threshold-Range Scaling of Excitable Cellular Automata," Statistics and Computing 1 (1991): 23--39 [Online]
• "Cyclic Cellular Automata in Two Dimensions," in Kenneth Alexander and Joseph Watkins (eds.), Spatial Stochastic Processes (Boston: Birkhauser, 1991), pp. 171--188 [Online]
• 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]
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
• 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
• 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"]
• 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
• 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