Cellular Automata
Last update: 24 Sep 2025 12:42
First version: Sometime in the 1990s (no earlier than 1995, maybe 1996?); last major revision 14 May 2002; tried to organize some links and clean up some link rot, 1 June 2025
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,
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:
- 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.
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, big picture:
- 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.]
- 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, big picture:
- Nino Boccara, Modeling Complex Systems
- Cellular Automata FAQ [ed. Tim Tyler, created by Howard Gutowitz]
- J. Doyne Farmer, Tommasso Toffoli and Stephen Wolfram
(eds.), Cellular Automata = Physica D 10 (1984): 1--247 [1983 conference at Los Alamos,
published as a book by Elsevier, and as a special issue of Physica
D, vol. 10, nos. 1--2]
- Howard A. Gutowitz (ed.), Cellular Automata: Theory and Experiment = Physica D 45 (1990): 1--483
- Andrew Ilachinski, Cellular Automata: A Discrete
Universe [Review by yours
truly and Cris Moore]
- Paul Manneville, Nino Boccara, Gérard Y. Vichniac and
Roger Bidaux (eds.), Cellular Automata and Modeling of Complex
Systems: Proceedings of the Winter School, Les Houches, France, February 21--28, 1989
Recommended, historical interest:
- Arthur W. Burks (ed.), Essays on Cellular Automata [Contributors
include Ulam and John Holland. One of my more
prized possessions.]
- John von Neumann, Theory of Self-Reproducing
Automata [edited, from a manuscript left not-quite complete when von Neumann died, by Burks]
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).]
- 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
- Gary D. Doolen (ed.), Lattice Gas Methods: Theory, Applications, and Hardware = Physica D 47 (1991): 1--339
- Gary Doolen, Uriel Frisch, Brosl Hasslacher, Steven Orszag and
Stephen Wolfram (eds.), Lattice Gas Methods for Partial Differential
Equations: A Volume of Lattice Gas Reprints and Articles, Including Selected
Papers from the Workshop on Large Nonlinear Systems, Held August, 1987, in Los
Alamos, New Mexico [SFI Proceedings Vol. IV, 1990]
- 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
- 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, close-ups on pure theory, abstract models, etc.:
- Remo Badii and Antonio Politi
- 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
- Geoffrey Grimmett, Probability on Graphs: Random Processes on Graphs and Lattices
- 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]
Recommended, close-ups, not otherwise categorized:
- Henryk Fukś, "Remembering Nino Boccara (1931--2018)", Journal of Cellular Automata 17 (2023): 461--477, arxiv:2312.14959
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
Klinkner and Robert Haslinger, "Quantifying Self-Organization with Optimal
Predictors", Physical Review Letters
93 (2004): 118701 = nlin.AO/0409024
To read, big picture:
- Franco Bagnoli, "Cellular Automata",
cond-mat/9810012
[introductory lecture notes]
- Bastien Chopard and Michel Droz, Cellular Automata Modeling
of Physical Systems
- 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."]
- 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]
- Voorhees, One-Dimensional Cellular Automata
To read, modeling applications:
- Mark S. Alber, Yi Jiang and Maria A. Kiskowski, "Lattice gas
cellular automata model for rippling and aggregation in myxobacteria", q-bio/0401014
- 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!]
- J. O. Indekeu and C. V. Giuraniuc, "Cellular automaton for
bacterial towers", Physica
A 336 (2004): 14--26
To read, lattice gas/lattice Boltzmann [with thanks to Luke Wagner for many recommendations]:
- 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
- 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
- U. Frisch, D. d'Humiéres, B. Hasslacher, P. Lallemand,
Y. Pomeau, J.-P. Rivet, Complex Systems 1 (1987):
649
- L. Kadanoff, G. McNamara, and G. Zanetti, Physical Review
A 40 4527 (1989)
- Jean-Pierre Rivet and Jean-Pierre Boon, Lattice Gas Hydrodynamics
- Sauro Succi, Iliya V. Karlin and Hudong Chen, "Role of the H
theorem in lattice Boltzmann hydrodynamic simulations,"
cond-mat/0205639
- 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
To read, least-action principles and H-theorems (see also under lattice gases and large deviations):
- Gianluca Caterina and Bruce Boghosian, "A "No-Go" Theorem for the
Existence of an Action Principle for Discrete Invertible Dynamical Systems",
nlin.CG/0611058
To read, applications to information-processing tasks:
- Franco Bagnoli, Andrea Guazzini, Emanuele Massaro, "Community-detection cellular automata with local and long-range connectivity", arxiv:1206.2262
- Olu Lafe, Cellular Automata Transforms: Theory and Applications in Multimedia Compression, Encryption, and Modeling
- 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?]
- 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]
To read, not otherwise, or not yet, classified:
- Andrew Adamatzky and Genaro J. Martinez (eds.), Designing Beauty: The Art of Cellular Automata
- A. P. F. Atman, R. Dickman, J. G. Moreira, "Phase diagram of a
probabilistic cellular automaton with three-site interactions,"
cond-mat/0210036
- F. Barra and P. Gaspard, "Classical Dynamics on Graphs,"
nlin.CD/0011045
- 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--206, arxiv:0902.1253
- 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?]
- Nazim Fates, "Directed percolation in asynchronous elementary
cellular automata: a detailed
study", nlin.CG/0703044
- 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
- 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
- Karl-Peter Hadeler and Johannes Müller, Cellular Automata: Analysis and Applications
- Brian P. Hoke,
Cellular Automata
and Art
- Wolfram Just, "Phase transitions in coupled map lattices and
in associated probabilistic cellular automata",
Physical Review
E 74 (2006): 046209
- 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
- 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
- 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
- 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
- Veronique Terrier, "Two-dimensional cellular automata and their
neighborhoods", 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
- Stanislaw Ulam, Adventures of a Mathematician
