author : Tommaso Toffoli

Contents

• Norman H. Margolus. Physics-like models of computation. Physica 10D. 1984

• Stephen Wolfram. Universality and complexity in Cellular Automata. 1984

• Douglas A. Lind. Applications of ergodic theory and sofic systems to Cellular Automata. 1984

• Michael S. Waterman. Some applications of information theory to Cellular Automata. 1984

• Peter Grassberger. Chaos and diffusion in deterministic Cellular Automata. 1984

Encode the 1D CA state …s_-2s_-1s₀s₁s₂… as the 2D point (0.s₀s₁s₂…, 0.s_-1s_-2…) • "similar" states are "close" in space (with a bias to similarity near cell c₀, consistent with the Cantor set topology explained in [Toffoli 1984a] below) •  time evolution is a trajectory in this space • some CA rules have dynamics that exhibit an "attractor"-like structure (although not completely identical) in this space

• T. E. Ingerson, R. L. Buvel. Structure in asynchronous Cellular Automata. 1984

asynchronous 1D CA investigations • random, and own clock • these models are more "natural" •  some self-organisin behaviour of synchronous 1D CAs comes from the synchronisation • some further interesting behaviour appears with asynchronous models

• Stephen J. Willson. Growth rates and fractional dimensions in Cellular Automata. 1984

• R. Wm. Gosper. Exploiting regularities in large cellular spaces. 1984

Optimisation algorithm for 2D CAs, using quadrant decomposition of cellular space, cacheing of results, and hashing to find previously used quadrants

• Gerard Y. Vichniac. Simulating physics with Cellular Automata. 1984

CAs exactly computable models, and non-numerical simulations • a naive CA implementation of a spin glass gives poor results

• Tommaso Toffoli. Cellular Automata as an alternative to (rather than an approximation of) differential equations in modeling physics. 1984

why CAs are appropraite for direct modelling of physical systems • Cantor set topology of infinite CAs

• Stephen M. Omohundro. Modelling Cellular Automata with partial differential equations. 1984

• Christopher G. Langton. Self-reproduction in Cellular Automata. 1984

requirement that self-replicator be a universal constructor is too strong: natural self-replicators (organisms!) aren't universal constructors • relax therequirement simply to: the "self-replicating" configuration must treat its stored information both as interpreted instructions and uninterpreted data • adaptation of Codd's 1968 universal constructor, with a different transition rule • states comprise instructions for constructing a new loop • instructions travel around the loop, memory - uninterpreted • instructions construct new loop - interpreted

• Stuart A. Kauffman. Emergent properties in random complex automata. 1984

N cells with boolean state, each getting input from K other randomly chosen cells, combined by a randomly chosen boolean function •  K = 2 dynamics properties : number of states = 2^N, yet cycle length, number of distinct cycles (basins of attraction) ~ N^1/2; cycles relatively stable to small perturbations •  canalising rules, and forcing structures - subgraphs that "crystallise" at their canalised values - and so partition the remaining graph into isolated subclusters •  as simple models of geneetic regulatory networks

• Christian Burks, J. Doyne Farmer. Towards modeling DNA sequences as automata. 1984

• Steven A. Smith, Richard C. Watt, Stuart R. Hameroff. Cellular Automata in cytoskeletal lattices. 1984

• Forrest L. Carter. The molecular device computer: point of departure for large scale Cellular Automata. 1984

• Tommaso Toffoli. CAM: a high-performance Cellular-Automaton Machine. 1984

support for "watching 2D CA evolution •  sequential processing, special-purpose hardware •  256x256 array of cells, periodic (toroidal) boundary conditions •  each cell with up to 256 states •  60 timesteps per second display

• Kendall Preston Jr. Four-dimensional logical transforms: data processing by Cellular Automata. 1984

• W. Daniel Hillis. The Connection Machine: a computer architecture based on Cellular Automata. 1984

• James P. Crutchfield. Space-time dynamics in video feedback. 1984