Cellular Automaton Approach

A cellular automaton (CA) is a computational model consisting of a grid of cells, each of which can be in one of a finite number of states. At each discrete time step, the state of each cell is updated according to a set of rules based on its current state and the states of its neighbors.

Most famously, John Conway introduced the “Game of Life” cellular automaton in 1970, which operates on a two-dimensional grid of cells that can be either “alive” or “dead.” Despite having only four rules, the Game of Life produces arbitrarily complex behavior—including universal computation.

Stephen Wolfram’s A New Kind of Science (2002) systematically explored a simpler class: elementary one-dimensional CAs. These operate on a linear tape of cells, each cell having only two states (0 or 1), and each cell’s next state determined by exactly three cells: itself and its two immediate neighbors.

Elementary Cellular Automata and Rule 110

An elementary CA operates on a 1D tape of binary cells. At each step, every cell’s new state is determined by the pattern of its left neighbor, itself, and its right neighbor—a three-cell window. Since each of the three cells can be 0 or 1, there are \(2^3 = 8\) possible input patterns. Since each pattern can map to 0 or 1, there are \(2^8 = 256\) possible elementary CA rules.

Wolfram numbered the rules by treating the output column as a binary number. Rule 110’s transition table is:

Input pattern (left, center, right):  111  110  101  100  011  010  001  000
New center cell:                         0    1    1    0    1    1    1    0

Reading the output row right-to-left gives the binary number \(01101110_2 = 110_{10}\), hence “Rule 110.”

Starting from a single live cell, Rule 110 evolves as follows (█ = 1, · = 0):

t=0:  · · · · · · █ · · · · · ·
t=1:  · · · · · █ █ · · · · · ·
t=2:  · · · · █ █ █ · · · · · ·
t=3:  · · · █ █ · █ · · · · · ·
t=4:  · · █ █ █ █ █ · · · · · ·
t=5:  · █ █ · · · █ · · · · · ·
t=6:  █ █ █ · · █ █ · · · · · ·

The pattern is neither purely periodic nor random; it produces structured, self-similar complexity from a single bit and eight output values.

Turing Completeness and the Principle of Computational Equivalence

In 2004, Matthew Cook proved that Rule 110 is Turing complete (Cook, 2004). Despite having the simplest possible structure in this system—a 1D binary tape, a three-cell neighborhood, a single fixed rule—Rule 110 can simulate any computation that a Turing machine can perform. This is, in a precise sense, the minimum structure needed for universal computation.

Wolfram’s A New Kind of Science frames this with the Principle of Computational Equivalence (PCE): among systems that are not obviously simple or periodic, virtually all exhibit computational behavior of equivalent sophistication. In other words, computational universality is not a rare property requiring elaborate machinery—it is the generic outcome once a system crosses a minimum complexity threshold.

The PCE has a direct corollary: once a system is universal, it is equivalent to every other universal system. A Turing machine, the lambda calculus, SKI combinatory logic, Rule 110, and Nock are all computationally equivalent. Any program expressible in one can be expressed in all others. The differences between them are not in what they can compute, but in how directly they express computation—the vocabulary and ergonomics of each model.

References

• Stephen Wolfram. (2002). A New Kind of Science. Wolfram Media.

• Matthew Cook. (2004). “Universality in Elementary Cellular Automata.” Complex Systems, 15(1), 1–40.

Nock as a Cellular Automaton

The cellular automaton model illuminates Nock from the angle of uniform rule application. The two systems share a common structure:

Cellular Automaton	Nock
Linear tape of binary cells	Binary tree of atoms and cells (a noun)
Cell state: 0 or 1	Node value: atom (natural number) or cell
Three-cell neighborhood	Subject + formula (the evaluation neighborhood)
Transition rule (e.g. Rule 110)	Evaluation function *[subject formula]
One time step → new tape configuration	One reduction step → result noun
Quiescent state (background of zeros)	Crash (undefined behavior, written !)
Universal (Rule 110 simulates any computation)	Universal (Nock is Turing complete)

The key structural parallel is uniform rule application. In an elementary CA, every cell on the tape applies the same transition rule—there is no special “controller” cell, no separate instruction memory. The rule is the only mechanism. In Nock, every sub-expression is evaluated by the same function *—there is no special-purpose runtime outside the spec. The opcodes encode all control flow within the noun itself.

The PCE reframes what Nock’s designers accomplished: Nock’s 12 opcodes are a careful choice of a minimum universal rule set. Just as Cook’s proof shows that Rule 110’s eight outputs are sufficient for universality, Nock’s specification shows that opcodes 0–5 are sufficient for universality (constant, increment, slot addressing, composition, and recursion), with opcodes 6–11 providing ergonomic extensions. Any system below this threshold cannot compute all computable functions; any system at or above it is equivalent to Nock in what it can ultimately express.

The difference in form is significant, though. An elementary CA encodes its computation in the spatial arrangement of cells across many time steps; a single glider in the Game of Life represents a moving signal that takes many cells and many ticks to traverse. Nock encodes its computation structurally in the noun tree, and a single reduction step can eliminate a whole subtree. The cellular automaton model is thus the most “horizontal” view of Nock: it spreads computation across parallel, simultaneous, local updates, while Nock collapses it into a single recursive evaluation.