BB(3)
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]
Champions
S(3) = 21 and there is only one shift champion (in TNF):
1RB1RZ_1LB0RC_1LC1LA(bbch)
Σ(3) = 6 and there are 5 ones champions (in TNF):
1RB1RZ_0RC1RB_1LC1LA(bbch)1RB1RC_1LC1RZ_1RA0LB(bbch)1RB1LC_1LA1RB_1LB1RZ(bbch)1RB1RA_1LC1RZ_1RA1LB(bbch)1RB1LC_1RC1RZ_1LA0LB(bbch)
Deciders
In order to prove BB(3), Lin discovered Translated Cyclers (which he called "partial recurrence") and described the first algorithm for proving them infinite.
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