Introduction

Imagine the simplest possible computer: a strip of tape full of zeros, a head that reads one cell, and a tiny rulebook of just a few states. Each rule says: given what you read, write a symbol, step left or right, and switch to another state — or halt.

Now play a game. Among all rulebooks with exactly n states that eventually stop, which one runs the longest before halting? That champion's step count is the Busy Beaver number, written BB(n).

It sounds like a harmless puzzle. With 1 state the record is 1 step; with 2 states, 6 steps. But the numbers don't grow — they erupt. And lurking inside this innocent game is a value that no computer, no matter how powerful, can ever calculate.

Run the Machines

Below are a few real Turing machines, each with just 2 or 3 states. Pick one and press Run. Watch the tape change, one rule at a time, and see whether it halts — and after how many steps.

<p class="hint">Each machine is a tiny rulebook of 2–3 <b>states</b> running on a tape of zeros. Pick one and press <b>Run</b>. Some halt fast, some run longer — and one never stops. You can <b>check</b> a finished run instantly, but you can't predict it without running it.</p>
<div class="picker">
  <button class="pick" data-m="bb2">BB(2) champion</button>
  <button class="pick" data-m="bb3">BB(3) champion</button>
  <button class="pick" data-m="loop">A non-stopper</button>
</div>
<div class="tape" id="tape"></div>
<div class="meta">
  <span id="state">state: &mdash;</span>
  <span id="steps">steps: 0</span>
</div>
<div class="status" id="status">Pick a machine, then Run.</div>
<div class="btns">
  <button id="run" type="button">Run</button>
  <button id="step" type="button" class="ghost">Step</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.picker { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .7rem; }
.pick { font: 600 13px system-ui, sans-serif; padding: .4rem .7rem; border: 1px solid #1d3557;
        background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; }
.pick.active { background: #1d3557; color: #fff; }
.tape { display: flex; gap: 3px; margin: .5rem 0; overflow-x: auto; padding: 4px 0; }
.cell { flex: 0 0 34px; height: 38px; display: flex; align-items: center; justify-content: center;
        font: 700 16px ui-monospace, monospace; border-radius: 6px; background: #eef2f6;
        border: 1px solid #d3dce4; color: #1d3557; }
.cell.one { background: #1d3557; color: #fff; border-color: #15263f; }
.cell.head { outline: 3px solid #e63946; outline-offset: 1px; }
.meta { display: flex; gap: 1.2rem; font: 600 .85rem ui-monospace, monospace; color: #44607a; margin: .2rem 0 .4rem; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button#run, button#step, button#reset { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
  border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A Busy Beaver "game": tiny Turing machines on a tape of 0s. A rule for
// (state, symbol) gives [write, move, nextState]. nextState 'H' = halt.
// Checking a finished run is a quick replay; predicting how long it runs —
// or whether it halts at all — is uncomputable in general (Radó, 1962).
//
// Machines below are the real records:
//  BB(2) champion: halts after 6 steps, writes four 1s.
//  BB(3) champion: the max-steps record, halts after exactly 21 steps (S(3)=21).
//  A non-stopper: a 2-state machine that loops forever.
const MACHINES = {
  bb2: { start: 'A', halts: 6, label: 'BB(2) champion', rules: {
    'A0': ['1','R','B'], 'A1': ['1','L','B'],
    'B0': ['1','L','A'], 'B1': ['1','R','H'] } },
  bb3: { start: 'A', halts: 21, label: 'BB(3) champion', rules: {
    'A0': ['1','R','B'], 'A1': ['1','L','H'],
    'B0': ['1','L','B'], 'B1': ['0','R','C'],
    'C0': ['1','L','C'], 'C1': ['1','L','A'] } },
  loop: { start: 'A', halts: null, label: 'A non-stopper', rules: {
    'A0': ['1','R','B'], 'A1': ['1','R','B'],
    'B0': ['1','L','A'], 'B1': ['1','L','A'] } }
};

let M = null, tape = null, pos = 0, state = '', steps = 0, halted = false, running = false;
const CAP = 4000; // safety cap so the page never freezes on a non-halter

function load(key){
  M = MACHINES[key];
  tape = {}; pos = 0; state = M.start; steps = 0; halted = false; running = false;
  document.querySelectorAll('.pick').forEach(b => b.classList.toggle('active', b.dataset.m===key));
  setStatus(fmt('Loaded %label%. Press Run.', { label: M.label }), '');
  render();
}
function read(){ return tape[pos] || '0'; }

function step(){
  if (halted) return;
  const rule = M.rules[state + read()];
  if (!rule){ halted = true; setStatus(fmt('Halted (no rule) after %steps% steps.', { steps: steps }), 'ok'); render(); return; }
  const [w, mv, next] = rule;
  tape[pos] = w;
  pos += (mv === 'R' ? 1 : -1);
  steps++;
  if (next === 'H'){ halted = true; render();
    setStatus(fmt('Halted after %steps% steps. (Record: %halts%)', { steps: steps, halts: M.halts }), 'ok'); return; }
  state = next;
  if (steps >= CAP){ halted = true; render();
    setStatus(fmt('Still running after %CAP% steps — this one never stops!', { CAP: CAP }), 'bad'); return; }
  render();
}

function run(){
  if (!M || running) return;
  running = true;
  const tick = () => {
    if (halted || !running){ running = false; return; }
    for (let i = 0; i < 1 && !halted; i++) step();
    if (!halted) requestAnimationFrame(tick); else running = false;
  };
  tick();
}

function render(){
  const t = document.getElementById('tape'); t.innerHTML = '';
  const lo = Math.min(pos - 5, -5), hi = Math.max(pos + 5, 5);
  for (let i = lo; i <= hi; i++){
    const d = document.createElement('div');
    const v = tape[i] || '0';
    d.className = 'cell' + (v === '1' ? ' one' : '') + (i === pos ? ' head' : '');
    d.textContent = v;
    t.appendChild(d);
  }
  document.getElementById('state').textContent = fmt('state: %v%', { v: halted ? 'HALT' : state });
  document.getElementById('steps').textContent = fmt('steps: %steps%', { steps: steps });
}
function setStatus(txt, cls){ const s = document.getElementById('status'); s.textContent = txt; s.className = 'status ' + cls; }

document.querySelectorAll('.pick').forEach(b => b.addEventListener('click', () => { running = false; load(b.dataset.m); }));
document.getElementById('run').addEventListener('click', run);
document.getElementById('step').addEventListener('click', () => { running = false; if (M) step(); });
document.getElementById('reset').addEventListener('click', () => { running = false; if (M) load(document.querySelector('.pick.active').dataset.m); });
load('bb3');
Result
Console

Notice the asymmetry. Checking a finished run is trivial: just replay it and count the steps. But predicting in advance how long a machine will run — or whether it stops at all — is the impossible part. The 3-state champion halts after 21 steps; another machine that looks just as simple never stops. There is no shortcut except to run it and wait, which is exactly the trap behind the halting problem.

The Real Complexity

How hard is the Busy Beaver, really? It is past hard — it is uncomputable.

  • Not in P, not in NP, not anywhere. BB(n) doesn't belong to a complexity class of slow algorithms. There is no algorithm at all that takes n and returns BB(n).
  • Radó's theorem (1962). The mathematician Tibor Radó proved that BB(n) is noncomputable and that it eventually dominates every computable function — it grows faster than any program could ever predict. The proof is a clean reduction from the halting problem: if you could compute BB(n), you could solve halting, which is impossible.
  • The numbers explode. BB(1)=1, BB(2)=6, BB(3)=21, BB(4)=107. Then BB(5) jumps to 47,176,870 — a result only fully settled in 2024 by the collaborative bbchallenge.org project. BB(6) is so vast it dwarfs the number of atoms in the universe, and its exact value will likely never be known.
  • A wall, not a hill. Some machines that resist analysis encode open math problems: a 27-state machine halts only if the Goldbach conjecture is false; a 744-state machine halts only if the Riemann hypothesis is false. Knowing their BB would settle famous conjectures.

That is the punchline: the Busy Beaver isn't a problem we haven't solved yet. It is a problem proven to sit beyond the reach of any algorithm forever — a concrete, countable number that computation can never name.

Where It Matters

A number you can never compute might sound useless — but the Busy Beaver is one of the sharpest tools we have for mapping the edge of the knowable:

  • The limits of computation. BB(n) is the cleanest possible companion to the halting problem: it turns "can we know if a program stops?" into a single, concrete, ever-growing number.
  • The limits of mathematics. Because some small machines halt only if a famous conjecture is true or false, BB encodes open questions. There is even an n beyond which BB(n) is independent of standard mathematics — provably unprovable.
  • Benchmarking reasoning. The hunt for BB(5) drove a global, crowd-sourced verification effort, pushing automated theorem-proving and machine analysis to new limits.
  • Intuition for the uncomputable. Most "impossible" results feel abstract. The Busy Beaver makes uncomputability tangible: here is a specific number, smaller than infinity, that no program will ever print.

Understand the Busy Beaver and you've grasped the same wall that bounds the halting problem and even P vs NP — except this wall is not about speed, but about what can be known at all.

Conclusion

The Busy Beaver begins as a game a child could play — write a few rules, run the machine, count the steps. Yet from those few rules emerges a number that outgrows every function, swallows famous conjectures, and provably lies beyond the reach of any computer.

So the next time someone says a faster machine can compute anything given enough time, remember BB(6). It is finite. It is a specific whole number. And no computer that will ever be built can tell you what it is. The Busy Beaver is the place where counting itself runs out of road — a quiet reminder that some truths are not slow to find, but impossible to reach, just like the wall behind the halting problem.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/busy-beaver/Content licensed under CC BY-NC 4.0.