InterJournal Complex Systems, 2
Status: Accepted
Manuscript Number: [2]
Submission Date: 940512
Occam, Turing, von Neumann, Jaynes: How much can you get for how little? (A conceptual introduction to cellular automata)
Author(s): Tommaso Toffoli

Subject(s): CX.04, CX.07

Category: Article


This is a introduction to cellular automata stressing their role as standard-bearers of an aggressive form of reductionism---which we may term "fine-grain modeling". Cellular automata try to capture in abstract computational terms certain fundamental aspects of physics---such as uniformity, locality, and local finiteness. At the same time, precisely because of this close match with physics, they provide a blueprint for very efficient fine-grained parallel computer architectures. The references to Occam, Turing, and von Neumann are canonical. The reference to Jaynes is in the following context. Recently, cellular automata have been found to be "unreasonably effective" in modeling by simple finitary means phenomena that are traditionally viewed as a preserve of differential equations and continuum methods. We try to show that there is really nothing unreasonable about this effectivenes. Much as the maximum-entropy (i.e., "most random") distribution obeying certain constraints is the a priori best guess for the unknown distribution underlying a given statistics, thus a "random" cellular automaton obeying certain constraints is a very good bet for a microscopic model of a given macroscopic dynamics.

Retrieve Manuscript
Submit referee report/comment

Public Comments: