Loading
Fetching the latest data…
Fetching the latest data…
Almost every open problem on this platform is open because the mathematics is hard. This one is open because it is IMPOSSIBLE — Turing proved in 1936 that no procedure can decide whether an arbitrary program halts, and Radó turned that proof into a game you can play. The machines are small enough to read in six lines. The numbers they produce are 6, 21, 107 — and then 47,176,870, which took forty years and a machine-checked proof. This path is the shortest honest route from "a program is just a table of instructions" to "and here is a specific question about them that nothing can answer".
Before you start — None. If you can follow "look at the square you are on, write something, move one step, do the next thing", you can read every machine in this lab. The advanced tier writes out the enumeration and the cycle-detection argument if you want to check the code.
A Turing machine here is a strip of blank squares, a head sitting on one of them, and a table with one row per (state, symbol) pair. Each row says three things: write a 0 or a 1, move left or right, and go to some state — or halt. That is the entire language. Everything a computer can do, any computer, is in there, which is Turing's point and the reason these tiny machines are worth taking seriously.
Do — Open the complete two-state sweep and read the champion's table under the chart. Six rows of the form `A0 → 1RB`. Follow it by hand on paper for the first three steps — the machine is small enough that you can, and doing it once makes the rest of this path concrete.
Fix the first move — write 1, go right, enter state B — and there are exactly 1,728 two-state machines. Not approximately: exactly. That is small enough to run every single one, which means the longest-running halting machine among them is not the best one found, it is THE longest one that exists. BB(2) = 6. This is the only place on this platform where a result stops being evidence and becomes a proof, and it is worth noticing how it felt: it took under a second and nothing dramatic happened.
Do — Look at three gauges together on that same sweep: Coverage 100, Record 100, Ones 100. Coverage 100 is what makes the other two mean something — the search ended. Then read the outcome counts and notice how many machines never halted at all.
A machine that has not halted in four hundred steps has told you nothing. It may halt on the four hundred and first — for five states, the champion takes forty-seven million. But there is one thing a sweep CAN prove: if a machine returns to a configuration it has already been in — same state, same head position, same tape — then, being deterministic, it will do the same thing again forever. The Decided gauge counts the machines whose fate is settled either way. Everything else is unknown, and unknown is not the same as never.
Do — Open the same three-state window at a step cap of 20, then again at 1000. Watch Decided climb — and watch it stop well short of 100 even at the top. The machines it cannot reach are not stuck. They are unproven.
Three states gives 1,048,576 machines, and exactly four of them run for 21 steps. Four in a million. That ratio is why busy beaver hunting is done by exhaustion rather than by exploration: there is no gradient to follow and no neighbourhood of a champion that is nearly as good. It is also why the numbers are so hard to establish — you cannot sample your way to a maximum you cannot recognise from nearby.
Do — Open the champions window: it holds one of the four. Read its table beside the two-state champion's and notice they are not related in any way you could have guessed. Then move the window yourself and try to find another.
Suppose you knew BB(6). Then to decide whether any six-state machine halts, you would run it for BB(6) steps and stop — if it has not halted by then it never will, because BB(6) is by definition the longest any halting six-state machine runs. That would decide the halting problem, which Turing proved cannot be decided. So BB is not computable: not hard to compute, not computable. BB(5) = 47,176,870 was settled in 2024 by a coordinated, machine-checked proof. BB(6) is open and is known to exceed a tower of fifteen tens. There is no method that gets the rest of them.
Do — Set the states to 4 and widen the window as far as it goes. Coverage reads 0 — truthfully, because a billion machines are out there. That gauge showing zero is the same situation the five-state problem was in for forty years, and the six-state problem is in now.
Out of the machines in your window, how many stopped on their own. Neither a high number nor a low one is a win. A window where everything halts is a window full of machines that did almost nothing; a window where nothing halts is one you cannot say much about. The interesting machines are the rare ones that run for a long time and then stop.
Try — Load Hasty and Patient one after the other. Same machines, same window, step cap 20 against 1000 — the halting share moves a long way, and nothing about the machines changed.
How many machines in your window you actually know the answer for. Two kinds count: the ones that stopped, and the ones caught going round in a circle — once a machine repeats a situation it has been in before, it will repeat it forever, so that is a proof. Everything else is simply unknown. Not "probably never stops" — unknown. Turning that unknown into a certainty for every machine is impossible, and that has been proved.
Try — Raise the step cap and watch this climb while the halting share climbs with it — then notice it stops well short of 100 no matter how high you go. The machines it cannot reach are not stuck; they are unproven.
The longest-running machine you found, compared with the longest one that exists for that number of states. 100 means your search found the champion. The numbers you are chasing are 6 steps for two states, 21 for three and 107 for four — small enough to write down, and it took mathematicians decades to be sure of the last one.
Try — Load Champions. It opens on the window of the three-state enumeration that contains a 21-step machine — read its transition table, then go and try to find another one by moving the window yourself.
The most ones any halting machine in your window left written on the tape, compared with the most that is possible. Running the longest and writing the most are different competitions, and they are usually won by different machines — a good reminder that "biggest" depends entirely on what you decided to measure.
Try — Run Complete — the whole two-state enumeration — and compare the two champion tables. Six steps and four ones are won by machines that differ in one transition.
How much of the whole space of machines your window looked at. At two states there are only 1,728 of them, so you can look at every single one — and then your answer is not a good guess, it is a proof. At four states there are more than a billion, and this gauge reads zero however wide you make the window. That gap is what the busy beaver problem is.
Try — Set the states to 2 and widen the window until coverage reads 100. Nothing else on this platform can do that, and the reason is that everything else has infinitely many configurations to try.
Surfacing sources you can verify is a deliberate anti-pseudoscience measure, not a bibliography. Nothing on this page asks to be taken on trust.
Glossary — every term used above, defined once.