
[1] D. Bell, Max, http://www.cs.jhu..edu/~callahan/patterns/max.html.
 [2] A. Condon, A theory of strict Pcompleteness. STACS 1992, in Lecture Notes in Computer Science 577 (1992) 33  44.

[3] R. Fisch and D. Griffeath, WinCA: a cellular automaton modeling environment.
Windows 3.x/95 software, version 1.0, 1996. Available from [7].

[4] E. Fredkin and T. Toffoli, Conservative logic. Int. J. Theor. Phys. 21 (1982) 219  253.

[5] J. Gravner and D. Griffeath, Cellular automaton growth on Z^{2}: theorems, examples, and open problems. In preparation.

[6] R. Greenlaw, H.J. Hoover, and W.L. Ruzzo, Limits to Parallel Computation: PCompleteness Theory. Oxford University Press, 1995.

[7] D. Griffeath. Primordial Soup Kitchen, http://math.wisc.edu/kitchen.html.

[8] Jörg Heitkötter, Zooland}, http://www.krl.caltech.edu/~brown/alife/zooland/.

[9] K. Lindgren and M.G. Nordahl, Universal Computation in Simple OneDimensional Cellular Automata. Complex Systems 4 (1990) 299  318.

[10] J. Machta and R. Greenlaw, The computational complexity of generating random fractals. J. Stat. Phys. 82 (1996) 1299.

[11] C. Moore, Quasilinear cellular automata. Santa Fe Institute Working Paper 9509078, to appear in Physica D, Proceedings of the International Workshop on Lattice Dynamics.

[12] C. Moore, NonAbelian cellular automata, Santa Fe Institute Working Paper 9509081, Predicting nonlinear cellular automata quickly by decomposing them
into linear ones, submitted to Physica D.

[13] C. Moore, MajorityVote Cellular Automata, Ising Dynamics, and PCompleteness.
Santa Fe Institute Working Paper 9608060, to appear in J. Stat. Phys.

[14] C. Moore and M.G. Nordahl, Lattice Gas Prediction is Pcomplete.
Santa Fe Institute Working Paper 9704034, available as compgas/9704001.

[15] C. Moore, The computational complexity of sandpiles. In preparation.

[16] N. Packard and S. Wolfram, Twodimensional cellular automata.
J. Stat. Phys. 38 (1985) 901  946, and private communication.

[17] C.H. Papadimitriou, Computational Complexity. AddisonWesley, 1994.
Acknowledgments. We thank Janko Gravner for help with the
LwoD figures and Dean Hickerson for expertise on the behavior of
LwoD's relatives. We also thank Rascal, Scurry, Oscar and Spootie
for companionship and inspiration.
Back
