How Cellular Automata Compute?

The Puzzle: Computation Without a Processor

The familiar image of computation is architectural. A conventional computer has memory, a processor, a clock, an instruction set, and a programme. A cellular automaton has none of these as named components. It has only a lattice of cells and a rule. Each cell reads a small neighbourhood and updates its own state. The rule is local, uniform, and usually very small. Nevertheless, the global evolution may carry information across space, create persistent structures, or simulate mechanisms that are computationally universal.

This is the conceptual inversion that makes cellular automata important. Computation is not identified with a particular physical architecture; it is identified with a structured transformation of encoded information. A transistor does not understand a spreadsheet, and a cell in a cellular automaton does not understand a Turing machine. In both cases, the semantics are supplied by a disciplined correspondence between physical or symbolic states and abstract objects. What changes is the substrate. In a conventional machine, the substrate is arranged into circuits and memory. In a cellular automaton, the substrate is arranged into space, locality, synchrony, and repeated rule application.

The idea also has a serious intellectual history. Von Neumann used cellular automata to study self-reproduction and the logical requirements of machines capable of constructing copies of themselves (von Neumann, 1966). Conway’s Game of Life later became the canonical demonstration that simple local rules can sustain moving patterns, signal routing, and universal computation (Berlekamp, Conway, and Guy, 1982; Rendell, 2011). Cook’s proof that Rule 110 is universal made the point still sharper: a one-dimensional, two-state, nearest-neighbour cellular automaton can simulate universal computation when supplied with the right initial configuration (Cook, 2004).

Formal Definition

A cellular automaton is most usefully defined as a global dynamical system induced by a local rule. Let A be a finite alphabet of cell states, and let the lattice be G, commonly Z for a one-dimensional automaton or Z² for a two-dimensional automaton. A configuration is a function from the lattice to the alphabet. The set of all configurations is therefore A^G. A local neighbourhood is a finite subset N of G, and a local rule is a function from neighbourhood patterns to a new state.

Cellular Automaton as a Discrete Dynamical System
├── Alphabet
│   └── A finite set A of possible cell states.
├── Lattice
│   └── A spatial index set G, usually Z or Z².
├── Configuration space
│   └── A^G, the set of all assignments of states to cells.
├── Neighbourhood
│   └── A finite set N ⊂ G used by the local rule.
├── Local rule
│   └── f: A^N → A.
└── Global map
    └── F: A^G → A^G, where each cell updates by applying f locally.

In one dimension with nearest-neighbour dependence, the global update has the form:

x_i(t + 1) = f(x_{i-1}(t), x_i(t), x_{i+1}(t))

This expression is deceptively modest. It says that every coordinate of the next configuration is computed from a finite window of the previous configuration, and that the same local function is used at every spatial position. The resulting global map is continuous in the product topology and commutes with spatial shifts. Conversely, the Curtis, Hedlund, and Lyndon characterisation states, in the one-dimensional symbolic-dynamical setting, that such continuous shift-commuting maps are precisely the maps generated by local cellular automaton rules (Hedlund, 1969). That theorem is important because it turns the informal phrase “local and translation-invariant” into an exact mathematical criterion.

What It Means For a Cellular Automaton To Compute

A cellular automaton does not compute merely because it produces complicated pictures. Computation requires an interpretation layer. There must be an encoding that embeds abstract input data into an initial configuration, a dynamical evolution under the cellular automaton rule, and a decoding that extracts an answer from a later configuration. If the decoded answer is the correct output for the encoded input, then the automaton has computed that function under the chosen representation.

Computation by Cellular Automaton
├── Abstract input
│   └── n, a bit string, a graph, a symbolic expression, or other data.
├── Encoding map
│   └── E(input) = initial configuration x(0).
├── Dynamics
│   └── x(t + 1) = F(x(t)), repeated for t time steps.
├── Observation region
│   └── A finite region, signal, phase, collision, or stable pattern.
└── Decoding map
    └── D(x(t)) = abstract output.

This definition mirrors ordinary computing more closely than it first appears. A binary integer inside a laptop is also an encoding. A voltage level is interpreted as a bit only because a hardware convention makes that interpretation reliable. The novelty of cellular automata lies not in the fact that interpretation is required, but in where the work is performed. Memory, control, and data movement are not cleanly separated. They are spatially distributed across evolving configurations.

A Mathematical Example: Rule 90 Computes Pascal’s Triangle Modulo Two

A better example than a phone-buying decision is a cellular automaton that performs a recognisable mathematical operation. Consider Rule 90, a one-dimensional binary cellular automaton. Each cell is either 0 or 1, and the update rule is the exclusive-or of the two neighbouring cells:

Rule 90

x_i(t + 1) = x_{i-1}(t) XOR x_{i+1}(t)

Since XOR is addition modulo two, this can be written over the finite field F₂ as:

x_i(t + 1) = x_{i-1}(t) + x_{i+1}(t)  mod 2

Now start from a single active cell at the origin:

x_i(0) = 1 if i = 0
x_i(0) = 0 otherwise

The first few time steps are:

t = 0:          1

t = 1:        1   1

t = 2:      1   0   1

t = 3:    1   1   1   1

t = 4:  1   0   0   0   1

These rows are Pascal’s triangle modulo two. More precisely, the configuration at time t consists of binomial coefficients reduced modulo two. The reason is algebraic. Represent a finite binary configuration by a Laurent polynomial over F₂:

X_t(z) = Σ_i x_i(t) z^i

Rule 90 multiplies this polynomial by z + z^-1 at each step:

X_{t+1}(z) = (z + z^-1) X_t(z)

Starting from X₀(z) = 1, after t steps we obtain:

X_t(z) = (z + z^-1)^t
       = Σ_{k=0}^t C(t, k) z^{t - 2k}  mod 2

Thus the cell at position t minus 2k is active exactly when the binomial coefficient C(t, k) is odd. The automaton has therefore computed a structured arithmetic object. It did not compute it by storing a loop counter, calling a binomial function, or executing an instruction sequence. It computed it by repeatedly applying a local linear update. The global mathematical object appears because repeated local addition over F₂ is equivalent to polynomial multiplication.

This example is instructive for graduate-level purposes because it separates three ideas that are often blurred. First, local rules can induce non-local algebraic structure. Second, the computation is representation-dependent: one must decide that the row at time t is to be decoded as the parity pattern of binomial coefficients. Third, complexity is not the same as universality. Rule 90 performs elegant linear computation, but linearity makes it too constrained to support arbitrary computation in the way Rule 110 or Conway’s Game of Life can.

Linear Cellular Automata and Why Universality Requires More

Rule 90 is a linear cellular automaton over F₂. If two initial configurations are added cellwise modulo two, their evolutions also add cellwise modulo two. In symbols:

F(x + y) = F(x) + F(y)

This linearity makes the automaton mathematically transparent. It also limits what it can do. Universal computation requires conditional control, memory, and interaction structures whose effects are not reducible to superposition. A universal cellular automaton must support something closer to programme-dependent behaviour: signals must collide differently depending on their phase, context, and arrangement. The boundary between Rule 90 and Rule 110 is therefore a useful conceptual boundary between algebraic pattern generation and general-purpose computation.

From Algebra to Signals: Gliders in Conway’s Game of Life

Conway’s Game of Life is a two-dimensional binary cellular automaton. A dead cell becomes alive if it has exactly three live neighbours. A live cell survives if it has two or three live neighbours and otherwise dies. These two rules are simple enough to state in one sentence, but their consequences are not merely decorative. Life supports stable objects, oscillators, moving objects, signal reflectors, duplicators, eaters, streams, and large engineered constructions.

The glider matters because it makes information transport explicit. If the presence of a glider on a channel represents 1 and its absence represents 0, then the automaton has a signal convention. If gliders can be delayed, reflected, duplicated, destroyed, or made to collide in controlled ways, then the automaton has the primitive components of circuit-like computation. In this setting, a “wire” is not copper. It is a reliable path through configuration space. A “gate” is not a transistor arrangement. It is a local region in which pattern collisions implement a truth-functional transformation.

The strong claim is not just that Life looks computational. Universal computer constructions in Life demonstrate that it can simulate Turing-equivalent machines (Berlekamp, Conway, and Guy, 1982; Rendell, 2011). The lesson is that universality arises when local dynamics can be engineered into reliable symbolic channels, memory structures, and controlled interactions.

Rule 110: A Universal Computer in One Dimension

Rule 110 is more austere than Life. It is one-dimensional, binary, and nearest-neighbour. Each cell updates according to the following table:

Rule 110

Current neighbourhood: 111 110 101 100 011 010 001 000
Next centre state:      0   1   1   0   1   1   1   0

Binary output sequence: 01101110
Decimal value:          110

Cook proved that Rule 110 is capable of universal computation by showing how its moving localised structures can emulate a cyclic tag system, which is itself computationally universal (Cook, 2004). The proof is not that an arbitrary random-looking Rule 110 pattern is a computer. The proof is that there exists a systematic encoding of computational data into an initial Rule 110 configuration such that the subsequent evolution simulates the steps of a universal computational model. In other words, Rule 110 is a computer not because every initial condition is meaningful, but because some initial conditions can be made to carry programme, data, and control.

This point is worth stressing. The single-cell animation is pedagogically useful because it shows that local rules can produce non-trivial spacetime structure. It is not, by itself, the universality construction. Universality is a stronger representational statement: there must be an encoding from arbitrary computations into initial configurations, and the cellular automaton dynamics must simulate those computations correctly.

Where Is the Programme?

In a conventional computer, the programme is typically a stored sequence of instructions. In a cellular automaton, the programme is commonly distributed across the initial configuration and the decoding convention. The update rule is fixed. It is more like the physics of the cellular universe than like a programme. The programme-like object is the carefully prepared pattern that determines what process unfolds under that fixed physics.

Conventional Computer
├── Hardware
│   └── Implements the low-level transition mechanism.
├── Programme
│   └── Stored instructions determine the computation.
├── Data
│   └── Stored and transformed through memory operations.
└── Output
    └── Read from a designated representation.


Cellular Automaton
├── Local rule
│   └── Fixed update law, analogous to the medium’s physics.
├── Initial configuration
│   └── Encodes data, machinery, and sometimes programme.
├── Evolution
│   └── Repeated global application of the same local rule.
└── Decoding convention
    └── Interprets a later pattern as the output.

This is why cellular automata sit naturally within unconventional computing. They demonstrate that computation can be performed by a spatially extended medium rather than by a central processor. The same region that stores information may also transmit and transform information. The separation between processor, memory, and wire is not assumed at the outset; it emerges, if at all, from stable structures in the dynamics.

The Formal Shape of Cellular Computation

A compact formal characterisation is as follows. Let A be a finite alphabet, let G be a lattice, and let F: A^G → A^G be the global cellular automaton map generated by a local rule. Let I be a set of abstract inputs and O a set of abstract outputs. The automaton computes a partial function φ: I → O if there exist an encoding E: I → A^G, a decoding D: A^G → O, and a halting or observation scheme such that:

D(F^T(E(u))) = φ(u)

for every input u in the domain of φ, where T may be a fixed time, an input-dependent halting time, or the first time at which a designated output region stabilises. Universal computation means that the same cellular automaton can simulate any Turing machine under an appropriate encoding. The local rule remains fixed; what varies is the initial configuration.

This definition also clarifies why the word “emergence” should be used carefully. Cellular automaton computation is emergent in the sense that global computational structure is not visible in any individual cell. It is not emergent in the sense of being inexplicable. Once encoding, dynamics, and decoding are specified, the computation is a rigorous object. The mystery is not that rules produce outputs. The interesting fact is that rules with such limited locality can support the full architecture of symbolic computation.

What Cellular Automata Teach Us About Computation

Cellular automata broaden the ontology of computation. They show that computation need not be attached to the familiar furniture of modern computers. A computation may be a spacetime pattern; a memory bit may be a stable configuration; a signal may be a glider; a logical operation may be a collision; a programme may be an initial condition. This does not make cellular automata magical. It makes computation more general than the machines through which most people encounter it.

The mathematical example of Rule 90 shows that even linear local rules can compute non-trivial arithmetic structure. The computational examples of Life and Rule 110 show that local rules can also be arranged into universal symbolic machines. Taken together, they suggest a mature view: cellular automata are neither merely visual curiosities nor automatic universal computers. They are discrete dynamical systems whose computational status depends on the existence of robust encodings, information-bearing structures, transformations, and decodings.

The central lesson is therefore precise. A cellular automaton acts as a computer when its evolving configurations can be made to represent, propagate, transform, store, and reveal information. The cells are individually simple; the computation belongs to the organised evolution of the whole configuration.

References