BB(2,4): Difference between revisions
Jump to navigation
Jump to search
(Improved introduction) |
(better description) |
||
| Line 1: | Line 1: | ||
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 2005. | 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 2005. | ||
On August 22, 2024, BB(2,4) = 3,932,964 was officially confirmed by the bbchallenge project, when a proof for the BB(2,4) case was added to [[Coq-BB5]] and successfully compiled. | 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 == | == History == | ||
Revision as of 11:56, 17 May 2025
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 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.[1]
- 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
References
- ↑ Brady A.H. (1988) The busy beaver game and the meaning of life in: The Universal Turing Machine: A Half-Century Survey, R. Herken (Ed.), Oxford University Press, 1988, 259-277.