BB(3)

From BusyBeaverWiki
Jump to navigation Jump to search

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.

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