BB(2,4)

The 2-state, 4-symbol Busy Beaver problem, BB(2,4), obtained a lower bound of BB(2,4) ≥ 3,932,964 when the winner was found in February 2005.

On August 22, 2024, BB(2,4) = 3,932,964 was officially confirmed by the bbchallenge.org massively collaborative research project, when a proof for the BB(2,4) case was added to Coq-BB5 and successfully compiled.

History

• Brady found a steps and ones champion in 1988, establishing S(2,4) ≥ 7195 and Σ(2,4) ≥ 90.
• Terry and Shawn Ligocki found the champion in 2005 but they did not prove it was BB(2,4).

Champion

S(2,4) = 3,932,964 and Σ(2,4) = 2050 and both are achieved by only one champion (in TNF):

• 1RB2LA1RA1RA_1LB1LA3RB1RZ (bbch)

Top Halters

The top 20 longest running BB(2,4) TMs (in TNF-1RB) are:

Standard Format           Status Steps   Σ
1RB2LA1RA1RA_1LB1LA3RB1RZ Halt   3932964 2050
1RB3LA1LA1RA_2LA1RZ3RA3RB Halt   7195    90
1RB3LA1LA1RA_2LA1RZ3LA3RB Halt   6445    84
1RB3LA1LA1RA_2LA1RZ2RA3RB Halt   6445    84
1RB2RB3LA2RA_1LA3RB1RZ1LB Halt   2351    60
1RB3RA1LA2RB_2LA3LA1RZ1RA Halt   1021    53
1RB3LA1RZ0RB_2LB2LA0LA0RA Halt   1001    26
1RB2LA1RZ3LA_2LA2RB3RB2LB Halt   770     30
1RB2LB1RZ3LA_2LA2RB3RB2LB Halt   708     29
1RB2LA0RB1LB_1LA3RA1RA1RZ Halt   592     24
1RB3LA3RA0LA_2LB1LA1RZ2RA Halt   392     20
1RB3LA1LA1RA_2LA1RZ2RB3RB Halt   376     21
1RB3LA1LA1RA_2LA1RZ0LA3RB Halt   376     21
1RB3LA3RB0LA_2LA1RZ1LB3RA Halt   374     22
1RB1RA1LB0RA_2LA3RB2RA1RZ Halt   335     18
1RB2LA3LA1LB_2LA1RZ2RB0RA Halt   292     18
1RB0RB1RZ0LA_2LA3RA3LA1LB Halt   289     13
1RB1LA1RZ0LB_2LA3RB1RB2RA Halt   283     18
1RB3LA3RA0LA_2LB1LA1RZ3RA Halt   266     19
1RB2RB1RZ1LB_2LA2LB3RB0RB Halt   241     15

For the top 100 halting BB(2,4) TMs, see: https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/2x4.txt