Universality and complexity in cellular automata

Wolfram, 1983, Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 601, 10.1103/RevModPhys.55.601

Comm. Math. Phys., to be published.

Lind, 1983

1984, Physica, 10D, 36

Wolfram, 1983, CA: an interactive cellular automation simulator for the Sun Workstation and VAX

T. Toffoli, N. Margolus and G. Vishniac, private demonstrations.

Billingsley, 1965

Knuth, 1981

Gallager, 1968

Farmer, 1982, Dimension, fractal measures and the probabilistic structure of chaos

J.D. Farmer, private communication.

Mandelbrot, 1982

Farmer, 1982, Information dimension and the probabilistic structure of chaos, Z. Naturforsch., 37a, 1304, 10.1515/zna-1982-1117

P. Grassberger, to be published.

P. Diaconis, private communication; C. Stein, unpublished notes.

Beckman, 1980

Hopcroft, 1979

Manna, 1974

Minsky, 1967

J. Milnor, unpublished notes.

Gosper, 1974, Life is universal

Berlekamp, 1982, vol. 2

Gosper, 1984, Exploiting regularities in large cellular spaces, Physica, 10D, 75

1979

Bennett, 1982, On the logical “depth” of sequences and their reducibilities to random sequences, IBM report