Wolfram Class IV complexity: gliders, collisions, universal computation
110Rule
IVWolfram Class
—Final density
YesTuring complete
Rule 110 is one of only a handful of elementary CAs proven Turing complete (Cook 2004, building on Wolfram's conjecture). It exhibits Wolfram Class IV behavior: neither periodic nor chaotic, but complex persistent structures (gliders) that interact and compute.
The rule maps each 3-cell neighborhood (L,C,R) → new center: 110 in binary = 01101110. Gliders emerge spontaneously from random or structured initial conditions and persist for thousands of generations. Their collisions implement logic gates, enabling universal computation.