Rule 110
An elementary cellular automaton where each cell's next state depends only on itself and its two neighbors — 3 cells, 8 possible patterns, one rule number. Rule 110 (01101110 in binary) is remarkable: it has been proven to be Turing complete.
Pattern (111→0, 110→1, 101→1, 100→0, 011→1, 010→1, 001→1, 000→0) = 01101110₂ = 110
Stephen Wolfram systematically studied all 256 elementary cellular automaton rules in the 1980s and classified them into four classes: uniform, periodic, chaotic, and complex. Rule 110 falls in class IV — the most interesting category — which Wolfram believed might be necessary for universal computation.
In 2004, Matthew Cook proved that Rule 110 is indeed Turing complete, meaning it can simulate any Turing machine and thus compute any computable function. This makes it one of the simplest known universal computers.
The proof involves encoding a computation as an initial pattern and showing that the rule's glider-like structures can interact to perform logical operations. Try Rule 30 for high-quality pseudo-random numbers, or Rule 90 for a Sierpinski triangle.