ITM · Recursively enumerable
BB(6) champion: runs longer than 2↑↑↑5 steps
The 6-state, 2-symbol Turing machine behind the best known lower bound on BB(6), found by mxdys in June 2025. Started on a blank tape it halts, but only after more than 2↑↑↑5 steps, a number no simulation will ever reach.
Behaviour
Whether it halts from a blank tape was not settled within the library’s step budget.
Notes
The current BB(6) champion, 1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE (standard text format; Z is the halt state), was discovered by mxdys in June 2025 as part of the bbchallenge collaboration. It proves the lower bound
BB(6) > 2 ↑↑↑ 5
in Knuth's up-arrow notation: 2 pentated to 5, a tower of 2s whose height is itself a tower of 2s, nested five levels deep. It beat the previous record, also set by mxdys that May, of BB(6) > 2 ↑↑ 2 ↑↑ 2 ↑↑ 9.
The proof that it halts does not come from running it. Its behaviour was analysed by hand and checked with accelerated simulators, which show that it repeatedly applies an iterated function whose growth is pentation. Stepping through it here shows the first few thousand steps: the rule-following structure is visible early, the halt is not.
Why it is interesting: BB(5) = 47,176,870 was settled in 2024 and formally verified in Coq. BB(6) is where the problem stops being tractable, several 6-state machines are open problems equivalent to Collatz-like conjectures, so every new champion also tightens our picture of where provability runs out.
Machine credit: mxdys (bbchallenge). Library entry and write-up: Shreyan Chaubey.