BB(2): Difference between revisions
Jump to navigation
Jump to search
(Confused me for a second, thinking there were 41 TMs that have the behavior of the champion →Halting TMs) |
|||
| Line 2: | Line 2: | ||
== Deciders == | == Deciders == | ||
The only decider needed to prove BB(2) is [[Translated Cycler]]. All 26 infinite TMs listed below are Translated Cyclers. | The only decider needed to prove BB(2) is [[Translated Cycler]]. All 26 infinite TMs listed below are either Translated Cyclers or Cyclers. | ||
== Champions == | == Champions == | ||
| Line 18: | Line 18: | ||
== Enumeration == | == Enumeration == | ||
In [[TNF-1RB]] there are exactly 41 2-state, 2-symbol [[TM]]s, of which 15 halt and 26 never halt. The last group can be divided to 3 [[Cycler|cyclers]] and 23 [[Translated Cycler|translated cyclers]]. | |||
=== Halting TMs === | === Halting TMs === | ||
The following TMs are ordered by the number of steps before halting and by the number of ones left in the tape (represented by the left and right numbers, respectively). | |||
<pre> | <pre> | ||
| Line 40: | Line 41: | ||
</pre> | </pre> | ||
=== | === Cyclers === | ||
The following TMs are ordered by the period and preperiod (represented by the left and right numbers, respectively). | |||
<pre> | <pre> | ||
1RB1RB_0LA--- | 1RB0RB_0LA--- Cycler 4 1 | ||
1RB1RB_0LA--- Cycler 2 1 | |||
1RB---_0LB1RB Cycler 2 1 | |||
</pre> | |||
1RB0RA_1LA--- | === Translated Cyclers === | ||
1RB0RA_0LA--- | <pre> | ||
1RB0LB_0LA--- | 1RB1RA_1LA--- Translated Cycler | ||
1RB0LA_1LA--- | 1RB1RA_0LA--- Translated Cycler | ||
1RB0LA_0LA--- | 1RB1LB_0LA--- Translated Cycler | ||
1RB---_1RB--- | 1RB0RA_1LA--- Translated Cycler | ||
1RB---_1RA--- | 1RB0RA_0LA--- Translated Cycler | ||
1RB---_1LB1RB | 1RB0LB_0LA--- Translated Cycler | ||
1RB---_1LB1LB | 1RB0LA_1LA--- Translated Cycler | ||
1RB---_1LB0RB | 1RB0LA_0LA--- Translated Cycler | ||
1RB---_1LB0LB | 1RB---_1RB--- Translated Cycler | ||
1RB---_1LB0LA | 1RB---_1RA--- Translated Cycler | ||
1RB---_0RB--- | 1RB---_1LB1RB Translated Cycler | ||
1RB---_0RA--- | 1RB---_1LB1LB Translated Cycler | ||
1RB---_1LB0RB Translated Cycler | |||
1RB---_0LB1RA | 1RB---_1LB0LB Translated Cycler | ||
1RB---_0LB1LB | 1RB---_1LB0LA Translated Cycler | ||
1RB---_0LB0RB | 1RB---_0RB--- Translated Cycler | ||
1RB---_0LB0RA | 1RB---_0RA--- Translated Cycler | ||
1RB---_0LB0LB | 1RB---_0LB1RA Translated Cycler | ||
1RB---_0LB0LA | 1RB---_0LB1LB Translated Cycler | ||
1RB---_0LB0RB Translated Cycler | |||
1RB---_0LB0RA Translated Cycler | |||
1RB---_0LB0LB Translated Cycler | |||
1RB---_0LB0LA Translated Cycler | |||
</pre> | </pre> | ||
== References == | == References == | ||
<references /> | <references /> | ||
Revision as of 15:03, 15 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 either Translated Cyclers or 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
In TNF-1RB there are exactly 41 2-state, 2-symbol TMs, of which 15 halt and 26 never halt. The last group can be divided to 3 cyclers and 23 translated cyclers.
Halting TMs
The following TMs are ordered by the number of steps before halting and by the number of ones left in the tape (represented by the left and right numbers, respectively).
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
Cyclers
The following TMs are ordered by the period and preperiod (represented by the left and right numbers, respectively).
1RB0RB_0LA--- Cycler 4 1 1RB1RB_0LA--- Cycler 2 1 1RB---_0LB1RB Cycler 2 1
Translated Cyclers
1RB1RA_1LA--- Translated Cycler 1RB1RA_0LA--- Translated Cycler 1RB1LB_0LA--- Translated Cycler 1RB0RA_1LA--- Translated Cycler 1RB0RA_0LA--- Translated Cycler 1RB0LB_0LA--- Translated Cycler 1RB0LA_1LA--- Translated Cycler 1RB0LA_0LA--- Translated Cycler 1RB---_1RB--- Translated Cycler 1RB---_1RA--- Translated Cycler 1RB---_1LB1RB Translated Cycler 1RB---_1LB1LB Translated Cycler 1RB---_1LB0RB Translated Cycler 1RB---_1LB0LB Translated Cycler 1RB---_1LB0LA Translated Cycler 1RB---_0RB--- Translated Cycler 1RB---_0RA--- Translated Cycler 1RB---_0LB1RA Translated Cycler 1RB---_0LB1LB Translated Cycler 1RB---_0LB0RB Translated Cycler 1RB---_0LB0RA Translated Cycler 1RB---_0LB0LB Translated Cycler 1RB---_0LB0LA Translated Cycler
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