BB(2): Difference between revisions
Jump to navigation
Jump to search
No edit summary |
m (Add TM Template) |
||
| Line 1: | Line 1: | ||
The 2-state 2-symbol Busy Beaver problem | 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.<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. <nowiki>https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</nowiki></ref> | ||
== Champions == | == Champions == | ||
S(2) = 6 and there are 5 shift champions in [[TNF]]: | S(2) = 6 and there are 5 shift champions in [[TNF]]: | ||
* {{TM|1RB1LB_1LA1RZ}} | |||
1RB1LB_1LA1RZ | * {{TM|1RB0LB_1LA1RZ}} | ||
1RB0LB_1LA1RZ | * {{TM|1RB1RZ_1LB1LA}} | ||
1RB1RZ_1LB1LA | * {{TM|1RB1RZ_0LB1LA}} | ||
1RB1RZ_0LB1LA | * {{TM|0RB1RZ_1LA1RB}} | ||
0RB1RZ_1LA1RB | |||
Σ(2) = 4 and there is one unique ones champion in TNF: | Σ(2) = 4 and there is one unique ones champion in TNF: | ||
* {{TM|1RB1LB_1LA1RZ}} | |||
1RB1LB_1LA1RZ | |||
== Enumeration == | == Enumeration == | ||
Revision as of 04:13, 12 July 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]
Champions
S(2) = 6 and there are 5 shift champions in TNF:
1RB1LB_1LA1RZ(bbch)1RB0LB_1LA1RZ(bbch)1RB1RZ_1LB1LA(bbch)1RB1RZ_0LB1LA(bbch)0RB1RZ_1LA1RB(bbch)
Σ(2) = 4 and there is one unique ones champion in TNF:
1RB1LB_1LA1RZ(bbch)
Enumeration
In TNF-1RB there are exactly 41 BB(2) TMs of which 15 halt:
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
and 26 are infinite:
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