Famous / interesting Turing machines

Parent: turing-machines

Beyond the busy-beaver — machines worth knowing, one per child.

The machines

• busy-beaver — max steps a halting n-state machine runs; uncomputable; with the S(1)/S(2) champions traced by hand.
• smallest-universal-tm — how small can a universal machine be (Rogozhin (4,6), Wolfram (2,3)).
• langtons-ant — a 2-rule 2-D machine: chaos, then an emergent "highway"; Turing-complete.
• rule-110 — a 1-D cellular automaton proved universal (Cook); universality is cheap.
• foundational-machines — explicit machines that halt iff ZFC is inconsistent / Goldbach / Riemann fail (Yedidia–Aaronson) — so BB(748) is independent of ZFC.