Rule 110

Rule 110 is a one-dimensional binary cellular automaton introduced by Stephen Wolfram in 1983. It is defined by a simple local update rule on a line of cells with nearest-neighbor interactions, yet it exhibits complex localized structures — gliders — that move and interact. In 2002, Matthew Cook proved that Rule 110 is Turing-complete: its glider dynamics suffice to simulate any Turing machine, making it the simplest known rule with universal computational power. The proof connects to complexity theory, emergence, and the Church-Turing thesis, demonstrating that universal computation does not require engineered hardware but emerges from minimal discrete rules. Rule 110 is the paradigmatic example of organized complexity in a one-bit cellular medium.