BB(3): Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
(Created page with "The 3-state 2-symbol Busy Beaver problem '''BB(3)''' was proven by Shen Lin in his 1963 doctoral dissertation<ref>Shen Lin. 1963. Computer studies of Turing machine problems. PhD dissertation. Ohio State University. https://etd.ohiolink.edu/acprod/odb_etd/etd/r/1501/10?clear=10&p10_accession_num=osu1486554418657614</ref> and republished in 1965.<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2):...")
 
(Added link to "champions")
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
The 3-state 2-symbol Busy Beaver problem '''BB(3)''' was proven by Shen Lin in his 1963 doctoral dissertation<ref>Shen Lin. 1963. Computer studies of Turing machine problems. PhD dissertation. Ohio State University. https://etd.ohiolink.edu/acprod/odb_etd/etd/r/1501/10?clear=10&p10_accession_num=osu1486554418657614</ref> and republished in 1965.<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2): 196–212. https://doi.org/10.1145/321264.321270</ref> Allen Brady independently proved it in his 1964 PhD dissertation.<ref>Allen Brady. 1964. Solutions of Restricted Cases of the Halting Problem Applied to the Determination of Particular Values of a Non-Computable Function. PhD dissertation. Oregon State University. https://ir.library.oregonstate.edu/downloads/6q182n74x</ref>
The 3-state 2-symbol Busy Beaver problem '''BB(3)''' was proven by Shen Lin in his 1963 doctoral dissertation<ref>Shen Lin. 1963. Computer studies of Turing machine problems. PhD dissertation. Ohio State University. https://etd.ohiolink.edu/acprod/odb_etd/etd/r/1501/10?clear=10&p10_accession_num=osu1486554418657614</ref> and republished in 1965.<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2): 196–212. https://doi.org/10.1145/321264.321270</ref> Allen Brady independently proved it in his 1964 PhD dissertation.<ref>Allen Brady. 1964. Solutions of Restricted Cases of the Halting Problem Applied to the Determination of Particular Values of a Non-Computable Function. PhD dissertation. Oregon State University. https://ir.library.oregonstate.edu/downloads/6q182n74x</ref>
== Techniques ==
In order to prove BB(3), Lin discovered [[Translated Cycler]]s (which he called "partial recurrence") and described the first algorithm for proving them infinite. Translated cycler (with cycler) deciders decide all except 63 TNF-1RB BB(3) TMs. Those last 63 are all decided by [[Closed Position Set (CPS)]] augmented with fixed history 1 (each symbol remembers the transition which wrote it).


== Champions ==
== Champions ==
S(3) = 21 and there is only one shift champion (in [[TNF]]):
S(3) = 21 and there is only one shift [[champion]] (in [[TNF]]):


* {{TM|1RB1RZ_1LB0RC_1LC1LA}}
* {{TM|1RB1RZ_1LB0RC_1LC1LA|halt}} leaves 5 ones


Σ(3) = 6 and there are 5 ones champions (in TNF):
Σ(3) = 6 and there are 5 ones champions (in TNF):


* {{TM|1RB1RZ_0RC1RB_1LC1LA}}
* {{TM|1RB1RZ_0RC1RB_1LC1LA|halt}} runs for 14 steps
* {{TM|1RB1RC_1LC1RZ_1RA0LB}}
* {{TM|1RB1RC_1LC1RZ_1RA0LB|halt}} runs for 13 steps
* {{TM|1RB1LC_1LA1RB_1LB1RZ}}
* {{TM|1RB1LC_1LA1RB_1LB1RZ|halt}} runs for 13 steps
* {{TM|1RB1RA_1LC1RZ_1RA1LB}}
* {{TM|1RB1RA_1LC1RZ_1RA1LB|halt}} runs for 12 steps
* {{TM|1RB1LC_1RC1RZ_1LA0LB}}
* {{TM|1RB1LC_1RC1RZ_1LA0LB|halt}} runs for 11 steps
BB(3) is notable for being the only known size where none of the shift champions are also ones champions.


== Deciders ==
== Enumeration ==
In order to prove BB(3), Lin discovered [[Translated Cycler]]s and described the first algorithm for proving them infinite.
In [[TNF-1RB]] there are exactly 4057 BB(3) TMs of which 1379 halt. The top longest running TMs are:<pre>
1RB1RZ_1LB0RC_1LC1LA Halt 21 5
1RB1RZ_0LC0RC_1LC1LA Halt 20 5
1RB1LA_0RC1RZ_1LC0LA Halt 20 5
1RB1RA_0RC1RZ_1LC0LA Halt 19 5
1RB0RA_0RC1RZ_1LC0LA Halt 19 4
1RB0LC_1LA1RZ_1RC1RB Halt 18 5
1RB0LB_0RC1RC_1LA1RZ Halt 18 5
1RB1LB_0RC1RZ_1LC0LA Halt 18 4
1RB0LB_0RC1RZ_1LC0LA Halt 18 3
1RB1RZ_0RC0RC_1LC1LA Halt 17 5
1RB1RZ_0RC---_1LC0LA Halt 17 4
1RB1LC_0LC1RA_1RZ1LA Halt 16 5
1RB0LC_1LC1RB_1RZ1LA Halt 16 5
1RB1LA_0LA1RC_1RA1RZ Halt 15 5
1RB1LA_0LA1RC_0RB1RZ Halt 15 4
1RB0LC_1RC1RZ_1LA0RB Halt 15 4
1RB0RB_0LC1RZ_1RA1LC Halt 15 3
1RB1RZ_0RC1RB_1LC1LA Halt 14 6
1RB1RZ_1LB0LC_1RA1RC Halt 14 5
1RB1RZ_0LC1RA_1LA1LB Halt 14 5
1RB1RZ_1LC1RA_1RC0LB Halt 14 4
1RB1RZ_1LB0LC_1RA0RC Halt 14 3
1RB1RZ_0LC0RB_1LA1LC Halt 14 3
1RB0RB_1LC1RZ_0LA1RA Halt 14 3
1RB1RZ_0LC0RA_1RA1LB Halt 14 2
</pre>For a full list of halting BB(3) TMs, see: https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x2.txt


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

Latest revision as of 10:50, 11 August 2025

The 3-state 2-symbol Busy Beaver problem BB(3) was proven by Shen Lin in his 1963 doctoral dissertation[1] and republished in 1965.[2] Allen Brady independently proved it in his 1964 PhD dissertation.[3]

Techniques

In order to prove BB(3), Lin discovered Translated Cyclers (which he called "partial recurrence") and described the first algorithm for proving them infinite. Translated cycler (with cycler) deciders decide all except 63 TNF-1RB BB(3) TMs. Those last 63 are all decided by Closed Position Set (CPS) augmented with fixed history 1 (each symbol remembers the transition which wrote it).

Champions

S(3) = 21 and there is only one shift champion (in TNF):

  • 1RB1RZ_1LB0RC_1LC1LA (bbch) leaves 5 ones

Σ(3) = 6 and there are 5 ones champions (in TNF):

  • 1RB1RZ_0RC1RB_1LC1LA (bbch) runs for 14 steps
  • 1RB1RC_1LC1RZ_1RA0LB (bbch) runs for 13 steps
  • 1RB1LC_1LA1RB_1LB1RZ (bbch) runs for 13 steps
  • 1RB1RA_1LC1RZ_1RA1LB (bbch) runs for 12 steps
  • 1RB1LC_1RC1RZ_1LA0LB (bbch) runs for 11 steps

BB(3) is notable for being the only known size where none of the shift champions are also ones champions.

Enumeration

In TNF-1RB there are exactly 4057 BB(3) TMs of which 1379 halt. The top longest running TMs are:

1RB1RZ_1LB0RC_1LC1LA Halt 21 5
1RB1RZ_0LC0RC_1LC1LA Halt 20 5
1RB1LA_0RC1RZ_1LC0LA Halt 20 5
1RB1RA_0RC1RZ_1LC0LA Halt 19 5
1RB0RA_0RC1RZ_1LC0LA Halt 19 4
1RB0LC_1LA1RZ_1RC1RB Halt 18 5
1RB0LB_0RC1RC_1LA1RZ Halt 18 5
1RB1LB_0RC1RZ_1LC0LA Halt 18 4
1RB0LB_0RC1RZ_1LC0LA Halt 18 3
1RB1RZ_0RC0RC_1LC1LA Halt 17 5
1RB1RZ_0RC---_1LC0LA Halt 17 4
1RB1LC_0LC1RA_1RZ1LA Halt 16 5
1RB0LC_1LC1RB_1RZ1LA Halt 16 5
1RB1LA_0LA1RC_1RA1RZ Halt 15 5
1RB1LA_0LA1RC_0RB1RZ Halt 15 4
1RB0LC_1RC1RZ_1LA0RB Halt 15 4
1RB0RB_0LC1RZ_1RA1LC Halt 15 3
1RB1RZ_0RC1RB_1LC1LA Halt 14 6
1RB1RZ_1LB0LC_1RA1RC Halt 14 5
1RB1RZ_0LC1RA_1LA1LB Halt 14 5
1RB1RZ_1LC1RA_1RC0LB Halt 14 4
1RB1RZ_1LB0LC_1RA0RC Halt 14 3
1RB1RZ_0LC0RB_1LA1LC Halt 14 3
1RB0RB_1LC1RZ_0LA1RA Halt 14 3
1RB1RZ_0LC0RA_1RA1LB Halt 14 2

For a full list of halting BB(3) TMs, see: https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x2.txt

References

  1. ↑ Shen Lin. 1963. Computer studies of Turing machine problems. PhD dissertation. Ohio State University. https://etd.ohiolink.edu/acprod/odb_etd/etd/r/1501/10?clear=10&p10_accession_num=osu1486554418657614
  2. ↑ Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". Journal of the ACM. 12 (2): 196–212. https://doi.org/10.1145/321264.321270
  3. ↑ Allen Brady. 1964. Solutions of Restricted Cases of the Halting Problem Applied to the Determination of Particular Values of a Non-Computable Function. PhD dissertation. Oregon State University. https://ir.library.oregonstate.edu/downloads/6q182n74x
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=BB(3)&oldid=3050"