Busy Beaver & the Halting Problem

Turing Machine

Speed 8 steps/s

Run State

state A · step 0

Steps executed

Ones on tape (score)

Head position

Current state

How it works

A Turing machine is a state Q, a tape alphabet Σ = {0,1}, and a transition function

δ: Q × Σ → Q × Σ × {L, R}

At every step it reads the symbol under the head, looks up δ(state, symbol), writes a new symbol, moves the head left or right, and switches state — until it enters HALT, or never does.

The busy beaver function Σ(n) is the largest number of 1s an n-state, 2-symbol machine can leave on the tape before halting; S(n) is the most steps it can take. Both are known exactly only for tiny n:

Σ(2)=4,  S(2)=6
Σ(3)=6,  S(3)=21
Σ(4)=13, S(4)=107
Σ(5)=4098, S(5)=47,176,870  (proved 2024)

Beyond n≈6 the values are known to depend on open problems in number theory — the function grows faster than any computable function of n.

Why "omnipotent" breaks here. Suppose a "halting oracle" H(M, input) existed that always correctly answers whether machine M halts. Build a machine D that runs H(D, D): if H says "halts", D loops forever; if H says "loops forever", D halts immediately. Either answer H gives is wrong about D — a contradiction. So no algorithm, however powerful, can decide halting for every machine. Try the "Simple non-halter" below: you can watch it run past any step cap you like and never be sure — from observation alone — that it won't halt on step one billion and one.

Machine select — swap between three provably-optimal busy beavers and a trivial machine that runs forever.
Run / Step — animate continuously at the chosen speed, or advance one transition at a time.
Reset — clears the tape and restarts the selected machine from state A.

Tape cell = 1 Tape cell = 0 Read/write head

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.