🤖 Turing Machine & Tibor Radó's Busy Beaver

Alan Turing (1936) • Tibor Radó's On Non-Computable Functions (Bell System Tech. J., May 1962)

Active State CardAScanning cell 0
Productivity σ(M)0Total 1s on tape (Radó Score)
Shift Count s(M)0Head shifts executed
Current Symbol0Next: 1RB
🎞️ Bi-Infinite Binary Tape (Σ = {0, 1})Click any cell to flip 0 ↔ 1 (or use Radó's strict all-0 blank tape)
-120
-110
-100
-90
-80
-70
-60
-50
-40
-30
-20
-10
00
▲A
10
20
30
40
50
60
70
80
90
100
110
120
⚡ ACTIVE RULEδ(A, 0) = (1, R, B) ➔ Write 1 at cell 0, shift head Right (R), go to State B.
🌌 2D Spacetime Worldline Diagram (Time Flows Downward ↓)Gold = 1 • Dark Slate = 0 • Cyan = Read/Write Head Trajectory

🦫 Tibor Radó's 1962 Busy Beaver Game Formulation

In May 1962, Hungarian mathematician Tibor Radó published “On Non-Computable Functions” in the Bell System Technical Journal (Vol. 41, pp. 877–884). To construct the simplest possible well-defined uncomputable function, Radó standardized the binary Turing Machine under five strict axioms:

  • 1. Binary Alphabet & Blank Tape: Alphabet Σ={0,1}\Sigma = \{0, 1\} on a two-way infinite tape initialized to all zeros.
  • 2. nn State Cards + Halt Card HH: Each state card qi∈{A,B,… }q_i \in \{A, B, \dots\} specifies two instruction lines (for scanned symbol 0 or 1).
  • 3. Mandatory Shift (D∈{L,R}D \in \{L, R\}): Every transition must shift Left (L) or Right (R)—stationary head moves are forbidden.
  • 4. Finite Search Space: For nn states, there are exactly N(n)=[4(n+1)]2nN(n) = [4(n+1)]^{2n} distinct machines.
  • 5. The Busy Beaver Score Σ(n)=max⁡M∈Enσ(M)\Sigma(n) = \max_{M \in E_n} \sigma(M): Among all halting nn-state machines, maximize the number of 1s left on the tape when halting (Σ(n)\Sigma(n)) and the maximum shifts before halting (S(n)S(n)).
🏆 Radó Busy Beaver Champions
🃏 Transition Table / State Cards (δ)Editable live
State Card AACTIVE
If Scan 0:1RB
If Scan 1:1LB
State Card B
If Scan 0:1LA
If Scan 1:0LC
State Card C
If Scan 0:1RH
If Scan 1:1LD
State Card D
If Scan 0:1RD
If Scan 1:0RA
📈 Known Busy Beaver Bounds (n = 1..6)
States nΣ(n) (Max 1s)S(n) (Max Shifts)Status / Year
n = 111Radó (1962)
n = 246Radó (1962)
n = 3621Lin & Radó (1965)
n = 413107Brady (1966)
n = 54,09847,176,870Coq Proven (2024)
n = 6≥ 10↑↑15≥ 10↑↑15Open (Pavel Kropitz)