BB(2): Difference between revisions
Jump to navigation
Jump to search
(Removed what I added and Shawn modified yesterday because it will likely soon be superseded by adding a BB(2,2) theorem to the Coq-BB5 code.) |
No edit summary |
||
| Line 18: | Line 18: | ||
== Enumeration == | == Enumeration == | ||
In [[TNF-1RB]] there are exactly 41 BB(2) [[TM]]s of which 15 halt: | |||
=== Halting TMs === | |||
In [[TNF-1RB]] there are exactly 41 BB(2) [[TM]]s of which 15 halt (the left digit represents the number of steps before halting and the right one the number of ones that are left out in the tape): | |||
<pre> | <pre> | ||
| Line 38: | Line 40: | ||
</pre> | </pre> | ||
=== Non-Halting TMs === | |||
There are also 26 machines that never halt: | |||
<pre> | <pre> | ||
Revision as of 19:10, 14 November 2024
The 2-state 2-symbol Busy Beaver problem BB(2) was solved by Tibor Radó using pencil and paper and announced in his seminal Busy Beaver paper, On Non-Computable Functions.[1]
Deciders
The only decider needed to prove BB(2) is Translated Cycler. All 26 infinite TMs listed below are Translated Cyclers.
Champions
S(2) = 6 and there are 5 shift champions in TNF:
1RB1LB_1LA1RZ(bbch) leaves 4 ones (the ones champion)1RB0LB_1LA1RZ(bbch) leaves 3 ones1RB1RZ_1LB1LA(bbch) leaves 3 ones1RB1RZ_0LB1LA(bbch) leaves 2 ones0RB1RZ_1LA1RB(bbch) leaves 2 ones
Σ(2) = 4 and there is one unique ones champion in TNF:
1RB1LB_1LA1RZ(bbch) runs for 6 steps (a shift champion)
Enumeration
Halting TMs
In TNF-1RB there are exactly 41 BB(2) TMs of which 15 halt (the left digit represents the number of steps before halting and the right one the number of ones that are left out in the tape):
1RB1LB_1LA1RZ Halt 6 4 1RB1RZ_1LB1LA Halt 6 3 1RB0LB_1LA1RZ Halt 6 3 1RB1RZ_0LB1LA Halt 6 2 1RB1LA_1LA1RZ Halt 5 3 1RB1LA_0LA1RZ Halt 5 2 1RB1RZ_1LB1RA Halt 4 2 1RB1RB_1LA1RZ Halt 4 2 1RB1RZ_1LB0RA Halt 4 1 1RB0RB_1LA1RZ Halt 4 1 1RB1RZ_1LA--- Halt 3 2 1RB---_1LB1RZ Halt 3 2 1RB1RZ_0LA--- Halt 3 1 1RB---_0LB1RZ Halt 3 1 1RB---_1RZ--- Halt 2 2
Non-Halting TMs
There are also 26 machines that never halt:
1RB1RB_0LA--- 1RB1RA_1LA--- 1RB1RA_0LA--- 1RB1LB_0LA--- 1RB0RB_0LA--- 1RB0RA_1LA--- 1RB0RA_0LA--- 1RB0LB_0LA--- 1RB0LA_1LA--- 1RB0LA_0LA--- 1RB---_1RB--- 1RB---_1RA--- 1RB---_1LB1RB 1RB---_1LB1LB 1RB---_1LB0RB 1RB---_1LB0LB 1RB---_1LB0LA 1RB---_0RB--- 1RB---_0RA--- 1RB---_0LB1RB 1RB---_0LB1RA 1RB---_0LB1LB 1RB---_0LB0RB 1RB---_0LB0RA 1RB---_0LB0LB 1RB---_0LB0LA
References
- ↑ Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x