BB(2): Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
(Added a link to specific code to classify all the BB(2) TMs and how to run the code.)
(Added link to "champions")
 
(10 intermediate revisions by 6 users not shown)
Line 1: Line 1:
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>
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>


== Current Work ==
== Deciders ==
Although the [[Coq-BB5]] proof contains a proof of this case, investigations are ongoing to make a simpler proof that better captures the complexity of this problem.
The only deciders needed to prove BB(2) are [[cycler]] and [[translated cycler]] deciders. All 26 infinite TMs listed below are either Translated Cyclers or Cyclers.
 
The following command which uses code from [https://github.com/sligocki/busy-beaver Shawn Ligocki's GitHub repository] to enumerate the BB(2) [[TM]]s in [[TNF]], run each of them for 1000 steps, and look for [[TM]]s that are [[Translated Cycler]]s which never halt:
      > lr_enum 2 2 1000 halt.txt infinite.txt holdout.txt false
This is all that is needed to classify all the BB(2) [[TM]]s so a minimal proof only has to have this functionality.


== Champions ==
== Champions ==
S(2) = 6 and there are 5 shift champions in [[TNF]]:
S(2)<ref>Same as BB(2).</ref> = 6 and there are 5 shift [[champions]] in [[TNF]]:


* {{TM|1RB1LB_1LA1RZ|halt}} leaves 4 ones (the ones champion)
* {{TM|1RB1LB_1LA1RZ|halt}} leaves 4 ones (the ones champion)
Line 22: Line 18:


== Enumeration ==
== Enumeration ==
In [[TNF-1RB]] there are exactly 41 BB(2) [[TM]]s of which 15 halt:
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]]s and 23 [[translated cycler]]s.
 
=== 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 42: Line 41:
</pre>
</pre>


and 26 are infinite:
=== 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 0
1RB1RA_1LA---
1RB1RB_0LA--- Cycler 2 1
1RB1RA_0LA---
1RB---_0LB1RB Cycler 2 1
1RB1LB_0LA---
</pre>
1RB0RB_0LA---
 
1RB0RA_1LA---
=== Translated Cyclers ===
1RB0RA_0LA---
The following TMs are classified (in order of appereance) by their period, the preperiod and by the offset (in absolute value):<pre>
1RB0LB_0LA---
1RB1RA_1LA--- Translated Cycler 4 4 2
1RB0LA_1LA---
1RB1LB_0LA--- Translated Cycler 4 3 2
1RB0LA_0LA---
1RB0RA_1LA--- Translated Cycler 4 0 2
1RB---_1RB---
1RB0LB_0LA--- Translated Cycler 4 0 2
1RB---_1RA---
1RB1RA_0LA--- Translated Cycler 3 1 1
1RB---_1LB1RB
1RB---_1LB1RB Translated Cycler 3 1 1
1RB---_1LB1LB
1RB---_0LB1RA Translated Cycler 3 1 1
1RB---_1LB0RB
1RB---_0LB0LA Translated Cycler 3 0 1
1RB---_1LB0LB
1RB0RA_0LA--- Translated Cycler 3 0 1
1RB---_1LB0LA
1RB0LA_1LA--- Translated Cycler 3 0 1
1RB---_0RB---
1RB0LA_0LA--- Translated Cycler 3 0 1
1RB---_0RA---
1RB---_1LB0LA Translated Cycler 3 0 1
1RB---_0LB1RB
1RB---_0LB0RA Translated Cycler 3 0 1
1RB---_0LB1RA
1RB---_1RA--- Translated Cycler 2 2 2
1RB---_0LB1LB
1RB---_0RA--- Translated Cycler 2 1 2
1RB---_0LB0RB
1RB---_1LB0RB Translated Cycler 1 5 1
1RB---_0LB0RA
1RB---_1LB0LB Translated Cycler 1 4 1
1RB---_0LB0LB
1RB---_0LB1LB Translated Cycler 1 4 1
1RB---_0LB0LA
1RB---_1LB1LB Translated Cycler 1 3 1
1RB---_0LB0RB Translated Cycler 1 3 1
1RB---_0LB0LB Translated Cycler 1 3 1
1RB---_0RB--- Translated Cycler 1 2 1
1RB---_1RB--- Translated Cycler 1 1 1
 
</pre>
</pre>


== References ==
== References ==
<references />
<references />
[[Category:BB Domains]]

Latest revision as of 10:23, 11 August 2025

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 deciders needed to prove BB(2) are cycler and translated cycler deciders. All 26 infinite TMs listed below are either Translated Cyclers or Cyclers.

Champions

S(2)[2] = 6 and there are 5 shift champions in TNF:

  • 1RB1LB_1LA1RZ (bbch) leaves 4 ones (the ones champion)
  • 1RB0LB_1LA1RZ (bbch) leaves 3 ones
  • 1RB1RZ_1LB1LA (bbch) leaves 3 ones
  • 1RB1RZ_0LB1LA (bbch) leaves 2 ones
  • 0RB1RZ_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 0
1RB1RB_0LA--- Cycler 2 1
1RB---_0LB1RB Cycler 2 1

Translated Cyclers

The following TMs are classified (in order of appereance) by their period, the preperiod and by the offset (in absolute value):

1RB1RA_1LA--- Translated Cycler 4 4 2
1RB1LB_0LA--- Translated Cycler 4 3 2
1RB0RA_1LA--- Translated Cycler 4 0 2
1RB0LB_0LA--- Translated Cycler 4 0 2
1RB1RA_0LA--- Translated Cycler 3 1 1
1RB---_1LB1RB Translated Cycler 3 1 1
1RB---_0LB1RA Translated Cycler 3 1 1
1RB---_0LB0LA Translated Cycler 3 0 1
1RB0RA_0LA--- Translated Cycler 3 0 1
1RB0LA_1LA--- Translated Cycler 3 0 1
1RB0LA_0LA--- Translated Cycler 3 0 1
1RB---_1LB0LA Translated Cycler 3 0 1
1RB---_0LB0RA Translated Cycler 3 0 1
1RB---_1RA--- Translated Cycler 2 2 2
1RB---_0RA--- Translated Cycler 2 1 2
1RB---_1LB0RB Translated Cycler 1 5 1
1RB---_1LB0LB Translated Cycler 1 4 1
1RB---_0LB1LB Translated Cycler 1 4 1
1RB---_1LB1LB Translated Cycler 1 3 1
1RB---_0LB0RB Translated Cycler 1 3 1
1RB---_0LB0LB Translated Cycler 1 3 1
1RB---_0RB--- Translated Cycler 1 2 1
1RB---_1RB--- Translated Cycler 1 1 1

References

  1. ↑ 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
  2. ↑ Same as BB(2).
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=BB(2)&oldid=3033"