A program made of a rule and a starting pattern
A cellular automaton has three ingredients. First, a grid of cells, which may be a single row, a flat plane or something higher-dimensional. Second, a small set of states for each cell, often just “off” and “on.” Third, an update rule that says what a cell becomes next, based on its own state and the states of its nearby cells, called its neighborhood.
Every cell applies the rule at the same moment. Then the new grid becomes the current one, and the process repeats. That is all. There is no instruction pointer, no memory separate from the cells and no loop written by the programmer. The loop is the passage of time.
If you want to treat this as programming, the rule is the fixed “machine” and the starting pattern is the program together with its input. The output is read from some later pattern, or from whether a particular region ever changes.
A small example you can follow by hand
Consider a single row of cells with a very simple rule: a cell becomes on if exactly one of its two neighbors, left or right, is on, and off otherwise. Cells beyond the edge count as off. This is a well-known elementary rule that behaves like an exclusive-or of the neighbors.
Start with one on cell in the middle of seven cells, writing X for on and a dot for off:
...X...
..X.X..
.X...X.
X.X.X.XCheck the second row: the cell just left of center has an on neighbor on its right and an off neighbor on its left, so it turns on. The center cell has two off neighbors, so it turns off. The same logic applies on the right. In the third row, the center cell sees two on neighbors, which is not exactly one, so it stays off. Keep going and the rows begin to trace a triangular pattern of nested gaps, a shape that also appears in other parts of mathematics.
Notice that no one wrote a drawing routine. The picture is a side effect of one tiny local rule applied again and again.
What changes when you program this way
Several habits from ordinary coding stop working.
- Everything happens in parallel. You cannot update cells one at a time and read the results of earlier cells within the same tick. An implementation needs two copies of the grid, or an equivalent trick.
- Information moves slowly. A cell only hears from its neighbors, so a signal can travel at most a fixed number of cells per tick. Programmers build signals out of moving patterns and use timing to coordinate them.
- Data and program are the same stuff. Both live in the cells. Moving a pattern is the closest thing to calling a function.
- Space is part of the algorithm. A task that is a short loop in normal code may need a carefully laid-out region, with wires and gates made of cell patterns.
If you have read about grid-based flow in Funge-style languages, the contrast is helpful. There, a single pointer travels across a playfield and cells sit still. Here, nothing travels except patterns, and every cell is active at once. Rules about grid edges matter in both cases: a toroidal playfield wraps around, and automata are often run on wrapped grids for the same convenience.
What can they compute
Some automata are limited. A one-dimensional rule that only ever produces simple repeating or fading patterns can be analyzed completely and does not do anything resembling general computation.
Others are far richer. Two famous examples, Rule 110 in one dimension and the Game of Life in two, are known to be capable of universal computation. This means that, given a suitable starting pattern, they can emulate a Turing machine, and so in principle perform any calculation an ordinary computer can. The caveat is the usual one: such a claim assumes an unbounded grid, which is closer to the idea of infinite memory than to any real machine.
Cellular automata are also tied to a different thread of research on self-reproduction, where early work looked at whether a pattern in a grid could build a copy of itself. That work is a reminder that these systems were studied as models of life and machines, not just as puzzles.
Why universality is not the same as usefulness
Knowing that an automaton is universal does not make it a pleasant programming system. Programs are huge, slow and fragile compared with the same logic in a normal language. The value is mostly conceptual. It shows how little is needed for computation and gives a concrete setting to ask about related questions, such as which properties of a rule can be decided in advance. For general rules, many such questions are undecidable, in the same spirit as the halting problem.
There is also a practical use closer to everyday engineering. Local-update grids are a natural fit for parallel hardware, and variants of the idea appear in simulations of physical and biological systems. How far that goes in any given field depends on the application.
Trying it yourself
A cellular automaton is one of the easiest “languages” to implement. A first version needs a list of cells, a function that computes the next list from the current one, and a loop that prints each generation. Start with one dimension, try different rules on a single on cell, and notice how often a rule that looks trivial produces something surprising. Then move to two dimensions, where the same ideas apply and patterns can move across the plane.