Computability playground

Busy Beaver Lab

A Busy Beaver is a tiny Turing machine that writes as many 1s as possible before halting. The rules look harmless. The search space turns volcanic almost immediately.

4ones for 2 states
6steps for 2 states
13ones for 4 states

Live tape

The classic 2-state champion starts on a blank tape.

Ready
Steps0
Ones0
StateA
Head0
Experiment

Edit the rules, then let the machine loose.

Each rule says: when the head reads 0 or 1 in a state, write a symbol, move left or right, and choose the next state. Reaching H halts the machine.

Rule table

Tip: build a small machine by changing one rule at a time, then use Step so the logic stays visible.

Challenge prompt

The 2-state champion prints four 1s in six steps. Can your altered rules halt with more, or do they run forever? There is no general shortcut that can always tell us.

Explosion

Small state counts, absurd outcomes.

Busy Beaver values grow faster than any computable function. Known exact values stop early, because proving a machine eventually halts can become harder than running it.

47,176,870

steps for the known 5-state value

The machine is tiny

Two symbols, a finite list of states, one tape head, and local rules. Nothing mystical is hidden in the model.

The question is brutal

Among machines that halt, which one writes the most 1s? The word “halts” carries the whole weight.

The boundary is real

Busy Beaver turns the halting problem into something you can watch move cell by cell.