BB(3): Difference between revisions
Jump to navigation
Jump to search
(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):...") |
(partial recurrence) |
||
| Line 15: | Line 15: | ||
== Deciders == | == Deciders == | ||
In order to prove BB(3), Lin discovered [[Translated Cycler]]s 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. | ||
== References == | == References == | ||
<references /> | <references /> | ||
Revision as of 03:34, 12 July 2024
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