author : Tommaso Toffoli

Contents

• Stephen Wolfram.

Universality and complexity in Cellular Automata

• Douglas A. Lind.

Applications of ergodic theory and sofic systems to Cellular Automata

• Michael S. Waterman.

Some applications of information theory to Cellular Automata

• Peter Grassberger.

Chaos and diffusion in deterministic Cellular Automata

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

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

• R. Wm. Gosper.

Exploiting regularities in large cellular spaces

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

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

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

• Christopher G. Langton.

Self-reproduction in Cellular Automata

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

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

• Steven A. Smith, Richard C. Watt, Stuart R. Hameroff.

Cellular Automata in cytoskeletal lattices

• Forrest L. Carter.

The molecular device computer: point of departure for large scale Cellular Automata

• Tommaso Toffoli.

CAM: a high-performance Cellular-Automaton Machine

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

• W. Daniel Hillis.

The Connection Machine: a computer architecture based on Cellular Automata

• James P. Crutchfield.

Space-time dynamics in video feedback

• Norman H. Margolus.

Physics-like models of computation. Physica 10D. 1984