The smallest universal machines

Parent: famous-machines

How little structure does universal computation need? A decades-long race to shrink the (states, symbols) of a universal Turing machine.

• Rogozhin (1996): a family of small universal machines, including a (4, 6) — 4 states, 6 symbols — and other tiny pairs ((2,18), (3,9), (5,5), …).
• Wolfram's (2, 3) machine: conjectured universal in A New Kind of Science; proved universal by Alex Smith (2007) — but under a non-standard input encoding (an infinite, non-periodic initial tape), so whether it counts as "really" universal is debated.

The lesson: universality is cheap — it appears in machines almost too small to do anything, which is why it's so hard to avoid (and why so many systems are accidentally Turing-complete). The boundary between "universal" and "not" is itself delicate — and where the encoding convention starts to matter.