BB(3): Difference between revisions
(→Champions: Note no shared champions) |
(Added link to "champions") |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 2: | Line 2: | ||
== Techniques == | == 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. | 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}} leaves 5 ones | * {{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}} runs for 14 steps | * {{TM|1RB1RZ_0RC1RB_1LC1LA|halt}} runs for 14 steps | ||
* {{TM|1RB1RC_1LC1RZ_1RA0LB}} runs for 13 steps | * {{TM|1RB1RC_1LC1RZ_1RA0LB|halt}} runs for 13 steps | ||
* {{TM|1RB1LC_1LA1RB_1LB1RZ}} runs for 13 steps | * {{TM|1RB1LC_1LA1RB_1LB1RZ|halt}} runs for 13 steps | ||
* {{TM|1RB1RA_1LC1RZ_1RA1LB}} runs for 12 steps | * {{TM|1RB1RA_1LC1RZ_1RA1LB|halt}} runs for 12 steps | ||
* {{TM|1RB1LC_1RC1RZ_1LA0LB}} runs for 11 steps | * {{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. | BB(3) is notable for being the only known size where none of the shift champions are also ones champions. | ||
| Line 49: | Line 49: | ||
== 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 steps1RB1RC_1LC1RZ_1RA0LB(bbch) runs for 13 steps1RB1LC_1LA1RB_1LB1RZ(bbch) runs for 13 steps1RB1RA_1LC1RZ_1RA1LB(bbch) runs for 12 steps1RB1LC_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
- ↑ 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
- ↑ 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
- ↑ 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