Rule 110 is one of only two elementary (1D, 2-state, radius-1) CAs proven Turing-complete (Cook 2004). Each cell's next state depends on its left neighbor, itself, and right neighbor. Rule 110 sits at the edge of chaos — producing complex, non-periodic patterns from simple initial conditions.