Prev: Rock of Gibraltar

Cellular Automata

Pioneered by Ulam and von Neumann, a cellular automaton (CA) is a formalism with the following characteristics.
  • there is a grid or lattice
  • each gridcell is a finite state machine (FSM), but as simple as possible. The entire grid is an autonomous FSM again.
  • there is speed of "light", the velocity at which information can travel across the grid
  • "the whole is less than the sum of its parts", since the input of the small FSMs is not arbitrary, but constrained to its neighbours
CAs have been used mainly as experimental mathematics (Ulam), artificial physics (Ulam), "new" physics (Wolfram), artificial life (von Neumann, Langton) or as a modelling tool (Toffoli). In biology the last case is the most interesting one. The features that make a CA a (good) model are:
  • structural stability: stable, but not too stable. When changing any parameter doesn't result in a structural effect, the model has no meaning (is not "saying" anything)
  • multiple stable points: starting in a certain initial state, a lot of stable states are possible
  • local optima: f.i. additive voting rules can be seen as minimizing the zero-one borderline
  • variable/FSM identification: the correspondence between the real world and the features in the model. The active components in CAs are not the FSMs but the spaces
  • dynamical systems constraints: fixed set of FSMs. When one relaxes these constraints, one gets individual oriented models
People started studying 1D elementary CAs and attempted to classify them by the temporal-spatial pattern they generated. The well-known classification by Wolfram is listed in the table below.

Spatial pattern
Non-spatial equivalent
to uniform pattern
fixed point
domains, localized: patches
limit cycles
domains, non-stationary: waves
limit cycles
non-periodic, non-localized
localized, long transient
universal computation

Particle conservation, biological models vs physical models
Space time scaling
behavior scaling
Synchronous vs asynchronous
critically slowing down phenomena
travelling patterns

Crutchfield's rule 54 (mesoscale pattern algebra)

Next: ?????