Mathematics
The Theory of Cellular Automata and Rule 110
Quick fact
Rule 110 is a one-dimensional cellular automaton that is Turing-complete, meaning it can simulate any computation, yet its local rule is simple enough to fit in a single line of code. This was proven in 2000 by Matthew Cook, a fact that surprised many because such a simple rule can exhibit such computational power.
Why this is interesting
What if a few simple rules applied to a row of cells could create something as powerful as a computer? Rule 110, a seemingly trivial automaton, does exactly that—and its behavior is so complex that it was only proven to be universal decades after its discovery.
Read the full explanation
Understanding The Theory of Cellular Automata and Rule 110
Imagine a row of cells, each either black or white. At each step, each cell looks at its neighbors (left, right, and itself) and changes color according to a fixed rule. The rule is local—each cell only cares about its immediate neighborhood. This is a cellular automaton: a discrete model that updates in time steps. Rule 110 is a specific rule for one-dimensional automata. It gets its name because the pattern of output bits (from the 8 possible neighborhoods) is 01101110 in binary, which equals 110 in decimal. Even with this simple rule, the behavior is astonishingly rich. When started from a random row, it produces a chaotic mix of patterns—some regular, some gliding, some evolving unpredictably. This is surprising because the rule is deterministic and local.
A deeper explanation
Why is Rule 110 Turing-complete? The key lies in its ability to emulate a universal computational model: the cyclic tag system. A cyclic tag system is a simple theoretical machine that manipulates a string of bits. It works in cycles: at each step, it reads the first bit of its data string, and depending on that bit, it appends a fixed string (from a list) to the end, then deletes the first bit. This might seem too simple, but cyclic tag systems are known to be computationally universal. Matthew Cook showed that Rule 110, when initialized with a particular periodic pattern (a 'glider' configuration), can encode and compute the evolution of any cyclic tag system. The gliders in Rule 110 act as the data strings and the rule itself implements the simple operations of cycling and string manipulation. So, despite its simplicity, Rule 110 can perform any computation, given the right initial conditions. This blurs the line between simple and complex, showing that complexity and computation can emerge from incredibly simple local interactions.