Rule 110 is an elementary 1D cellular automaton where each cell's next state depends only on itself and its two neighbors. Matthew Cook proved in 2004 that Rule 110 is Turing-complete — capable of universal computation — despite its extremely simple local rule. Complex, self-organizing patterns emerge spontaneously.