My papers

The primary papers that I published about cellular automata and other issues related to this book were (the dates indicate when I finished my work on each paper; the papers were actually published 6-12 months later):

• "Statistical mechanics of cellular automata" (June 1982) (introducing 1D cellular automata and studying many of their properties)

• "Algebraic properties of cellular automata" (with Olivier Martin and Andrew Odlyzko) (February 1983) (analyzing additive cellular automata such as rule 90)

• "Universality and complexity in cellular automata" (April 1983) (classifying cellular automaton behavior)

• "Computation theory of cellular automata" (November 1983) (characterizing behavior using formal language theory)

• "Two-dimensional cellular automata" (with Norman Packard) (October 1984) (extending results to two dimensions)

• "Undecidability and intractability in theoretical physics" (October 1984) (introducing computational irreducibility)

• "Origins of randomness in physical systems" (February 1985) (introducing intrinsic randomness generation)

• "Random sequence generation by cellular automata" (July 1985) (a detailed study of rule 30)

• "Thermodynamics and hydrodynamics of cellular automata" (with James Salem) (November 1985) (continuum behavior from cellular automata)

• "Approaches to complexity engineering" (December 1985) (finding systems that achieve specified goals)

• "Cellular automaton fluids: Basic theory" (March 1986) (deriving the Navier-Stokes equations from cellular automata)

The ideas in the first five and the very last of these papers have been reasonably well absorbed over the past fifteen or so years. But those in the other five have not, and indeed seem to require the whole development of this book to be able to present in an appropriate way.

Other significant publications of mine providing relevant summaries were (the dates here are for actual publication—sometimes close to writing, but sometimes long delayed):

• "Computers in science and mathematics" (September 1984) (*Scientific American* article about foundations of the computational approach to science and mathematics)

• "Cellular automata as models of complexity" (October 1984) (*Nature* article introducing cellular automata)

• "Geometry of binomial coefficients" (November 1984) (additive cellular automata and nested patterns)

• "Twenty problems in the theory of cellular automata" (1985) (a list of unsolved problems to attack—most now finally resolved in this book)

• "Tables of cellular automaton properties" (June 1986) (features of elementary cellular automata)

• "Cryptography with cellular automata" (1986) (using rule 30 as a cryptosystem)

• "Complex systems theory" (1988) (1984 speech suggesting the research direction for the new Santa Fe Institute)