Cellular Automata FAQ


[Non-Java version]

Particular rules

Collapse all tree nodesExpand all tree nodes
Expand this node
Expand/collapse
Expand this node
What is the Fredkin rule?

Contributions by:

Joseph J. Strout <jstrout@ucsd.edu> Strout

The rule is described in The Armchair Universe by A.K. Dewdney, p. 24. It's a simple rule: the cell becomes "alive" iff the number of living neighbors is odd. (Assuming cells are represented as 0 and 1, you can write c = sum(c,N) neighborhood, Fredkin's rule has the fascinating property that any initial pattern is replicated several times on a larger scale. If you're using four neighbors (rectangular orthogonal), you get four copies of the initial starting pattern, then 16, then 64, and so on, every so many ticks. It works for neighborhood sizes of 6 and 8, too.

Expand this node
Expand/collapse
Expand this node
Where can I read about the Gacs rule?

Contributions by: Lenore Levine <levine@symcom.math.uiuc.edu>

The first paper on the Gacs rule was published in Problems of Transmission of Information, in 1978. The Russian journal has been translated into English. There are two co-authors, Kurdyumov and Levin.

Here are a few later papers that are probably related: [Gac83] [GR85] [G\'86] [GR88] [G\'89]

One piece of further work is this: [dSM92]

Some related papers:

[Gra82]; this is Gray's proof of ergodicity for continuous-time monotonic nearest-neighbor rules.

[Gra87]; this is Gray's proof for discrete time.

[BS88] This is a relatively simple proof of Toom's rule.

[G\'86] This is my Gacs' 1 dimensional construction.

[G\'89] This is a 2-dimensional construction which may help understanding the difficult 1-dimensional paper and has a little more general discussion.

Expand this node
Expand/collapse
Expand this node
What are filter automata?

Contributions by: Pawel Siwak <PSIW@agat.sk-kari.poz.edu.pl>

See a paper by Pawel Siwak Filtrons and their associated ring computations

Expand this node
Expand/collapse
Expand this node
What's the Hodge-Podge rule?

What's the Hodge-Podge Rule?

Contributions by: Jörg Heitkötter <joke@santafe.edu>

HODGE-C is a (`mostly ANSI') C language implementation of Gerhard & Schuster's hodge-podge machine. It implements a class of cellular automata, that resemble very closely autocatalytic chemical reactions, like for example, the Belousov-Zhabotinskii (BZ) reaction. It's available via anonymous ftp from HODGE

Cellular-3.0 include a hodge-podge rule.

And see Jörg Heitkötter's home page for pictures of the Hodge-Podge rule in action.

and hodge for a C program.

References

BZ specific publications:

[Dew88a] [MPH85] [MPH87] [MF87] [Dew89] [Dew88b] [Dur91] [Win74]

General CA: [Lan89] [Lea90]

Introductory books: [Dav88] [BP89]

Expand this node
Expand/collapse
Expand this node
What are some good references on Eater rules?

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

[DS91] [Eps91] [GHH78a] [GHH78b] [GGH80] [MF83] [Mur88] [Win74] [WWS85]

Expand this node
Expand/collapse
Expand this node
What are Vants?

What are Vants?

Contributions by:

John N. Rachlin <rachlin@cs.jhu.edu> Charles F. Wells <cfw2@po.CWRU.Edu> A Fraser <A.Fraser@eee.salford.ac.uk> Rudy Rucker <rucker@jupiter.SJSU.EDU>

The Vant rule, by Chris Langton, describes the path of an ant who starts pointing in a certain direction. If the ant is on a non-white square it turns the square red, rotates 90 degrees clockwise and moves one pixel in the direction it is pointing. If it is on a red square it turns the square white, rotates 90 degrees counterclockwise and moves one pixel in the direction it is pointing.

A generalization of Lanton's Ant can be found in Rudy Rucker, ARTIFICIAL LIFE LAB, Waite Group Press.

There were also some articles about Lanton's Ant in Dewdney's magazine Algorithm, and I believe there was an article in The Mathematical Intelligencer. Langton's original article in the reference cited by Dewdney is well worth looking up.

See: [Lan86]

Some vant simulators

Langtons_Ants

by John N. Rachlin <rachlin@blaze.cs.jhu.edu>

description: This program is based on "Langton's Automaton" and demonstrates the complex patterns of one or more "ants" moving according to simple user-defined rules.

requirements: This Program was written in Turbo Pascal, ver. 6.0 and Turbo C 2.0 It requires EGA or VGA graphics. An executable is available from the author.

Quick Basic Vants

Description: This program implements Chris Langton's cellular automaton [unk93]

requirements: This is a QBasic program that can be run on any DOS machine with VGA graphics. It was written by Charles Wells, Department of Mathematics, Case Western Reserve University, Cleveland, OH 44106-7058, USA. <cfw2@po.cwru.edu.>

Virtual Ants in C

Borland C port of above by <A.Fraser@eee.salford.ac.uk>.

A generalization of Lanton's Ant can be found in Rudy Rucker, ARTIFICIAL LIFE LAB, Waite Group Press.

Expand this node
Expand/collapse
Expand this node
What is known about Hexagonal CA?
Contributions by:

Charles Herring <herring@pike.cecer.army.mil> Herring McIntosh Harold V.-UAP <mcintosh@redvax1.dgsca.unam.mx> <gaylord@ux1.cso.uiuc.edu> richard j. gaylord

Programs

For a C++ / unix/X computer program, see: Hex Prog The source code is available Hex FTP

Gaylord: I've written a CA which treats the hexagonal lattice as a distorted square lattice and i've used it to implement the snowflake formation model of Packard in Mathematica.

References

A good reference on hexagonal CA is:

Kendall Preston, Jr. and Michael J. B. Duff, Modern Cellular Automata, Plenum Press, New York, 1984 (ISBN 0-306-41737-5).

These authors were mostly interested in filtering and sharpening digital images, but there are a couple of chapters on more general automata. In particular, they found some rules with gliders, and quite a few with oscillators. However, nobody seems to have yet found a rule with glider guns, so that it is hard to go on and get the other constructions which make Life interesting.

Expand this node
Expand/collapse
Expand this node
What about other types of lattices?

What about other types of lattices?

Contributions by: Dr. Olivier Baujard <baujard@cih.hcuge.ch>

Baujard: I'm using Voronoi (Dirichlet) tesselations as lattices for my CA. For an example of such lattices, have a look at: tesselation

Expand this node
Expand/collapse
Expand this node
References
BP89
John Briggs and F. David Peat. An Illustrated Guide to Chaos Theory and the Science of Wholeness. Harper & Row, New York, 1989.

BS88
Piotr Berman and Janos Simon. Investigations of fault-tolerant networks of computers. In Proc. of the 20-th Annual ACM Symp. on the Theory of Computing, pages 66-77, 1988.

Dav88
Paul Davies. Cosmic Blueprint. Heinemann, London, 1988.

Dew88a
A. K. Dewdney. The Armchair Universe, volume ISBN 0-7167-1939-8 pbk. W. H. Freeman and Company, New York, 1988.

Dew88b
A. K. Dewdney. Computer recreations: The hodgepodge machine makes waves. Scientific American, pages 104-107, August 1988.

Dew89
A. K. Dewdney. Computer recreations: A cellular universe of debris, droplets, defects and demons. Scientific American, pages 102-105, August 1989.

DS91
Richard Durrett and Jeffrey E. Steif. Some rigorous results for the greenberg-hastings model. Journal of Theoretical Probability, 4:669-690, 1991.

dSM92
Paula Gonzaga de Sá and Christian Maes. The Gács-Kurdyumov-Levin Automaton revisited. Journal of Statistical Physics, 67(3/4):607-622, May 1992.

Dur91
Rick Durret. Some new games for your computer. Nonlinear Science Today, 1(4):1-7, 1991.

Eps91
Irving R. Epstein. Spiral waves in chemistry and biology. Science, 252:67, 1991.

G86
Peter Gács. Reliable computation with cellular automata. Journal of Computer and Systems Science, 32(1):15-78, February 1986.

G89
Peter Gács. Self-correcting two-dimensional arrays. In Silvio Micali, editor, Randomness in Computation, volume 5 of Advances in Computing Research (a scientific annual), pages 223-326. JAI Press, Greenwich, Conn., 1989.

Gac83
P. Gacs. Reliable computation with cellular automata. In Proc. 15th ACM Symposium on Theory of Computing (STOC), pages 32-41, 1983.

GGH80
J. M. Greenberg, C. Greene, and S. Hastings. A combinatorial problem arising in the study of reaction-diffusion equations. SIAM Journal of Algebra and Discrete Mathematics, 1:34-42, 1980.

GHH78
J. M. Greenberg, B. D. Hassard, and S. P. Hastings. Pattern formation and periodic structures in systems modelled by reaction-diffusion equations. Bulletin of the American Mathematical Society, 84:1296-1327, 1978.

GR85
P. Gacs and X. Reif. A simple three-dimensional real-time reliable cellular array. STOC, 1985.

GR88
P. Gacs and X. Reif. A simple three-dimensional real-time reliable cellular array. JCSS, 36, 1988.

Gra82
Lawrence F. Gray. The positive rates problem for attractive nearest neighbor spin systems on z. Z. Wahrscheinlichkeitstheorie verw. Gebiete, 61:389-404, 1982.

Gra87
Lawrence F. Gray. The behavior of processes with statistical mechanical properties. In Percolation Theory and Ergodic Theory of Infinite Particle Systems, pages 131-167. Springer-Verlag, 1987.

Lan86
C. G. Langton. Studying artificial life with cellular automata. Physica D, 22:120-149, 1986.
A preliminary investigation of the potential of CA for supporting life.

Lan89
Christopher G. Langton. Artificial Life. Addison-Wesley, Redwood City, CA, 1989.

Lea90
Christopher G. Langton and et al. Artificial Life II. Addison-Wesley, Reading, MA, 1990.

MF83
Barry F. Madore and Wendy L. Freedman. Computer simulations of the belousov-zhabotinsky reaction. Science, 222:615-616, 1983.

MF87
B. F. Madore and W. L Freedman. Self-organizing structures. American Scientist, 75:252-259, 1987.

MPH85
Stefan C. Muller, Theo Plesser, and Benno Hess. The structure of the core of the spiral wave in the B-Z reaction. Science, 230:4726, November 1985.

MPH87
Stefan C. Muller, Theo Plesser, and Benno Hess. Threedimensional representation of chemical gradients. Biophysical Chemistry, February 1987.

Mur88
James D. Murray. How the leopard gets its spots. Scientific American, pages 62-69, March 1988.

unk93
unknown. Chris langton's cellular automaton (?). Mathematical Intelligencer, 15(2):54, 1993.

Win74
Arthur T. Winfree. Rotating chemical reactions. Scientific American, pages 82-95, June 1974.

WWS85
A. T. Winfree, E. M. Winfree, and H. Seifert. Organizing centers in a cellular excitable medium. Physica D, 17:109-115, 1985.