BB(3): Difference between revisions
Jump to navigation
Jump to search
(partial recurrence) |
(Add some longest running halters) |
||
| 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. | |||
== Champions == | == Champions == | ||
| Line 14: | Line 17: | ||
* {{TM|1RB1LC_1RC1RZ_1LA0LB}} | * {{TM|1RB1LC_1RC1RZ_1LA0LB}} | ||
== | == Enumeration == | ||
In | 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 /> | ||
Revision as of 03:43, 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]
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)
Σ(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)
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