1D cellular automaton Rule 110, proven Turing-complete by Matthew Cook. Complex, irregular patterns emerge from a simple 3-cell neighborhood rule.