Skelet 1: Difference between revisions
Add new preperiod computation |
m →Behavior: Fixed a typo. |
||
| (13 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{machine|1LC1LE_---1LD_1RD0LD_1LA1RE_0LB0RC | {{machine|1LC1LE_---1LD_1RD0LD_1LA1RE_0LB0RC}}{{unsolved|What is the exact cycle preperiod of Skelet 1?}}{{Stub}} | ||
[[File:Skeleton warrior.png|thumb|A skeleton warrior holding a sword. The runic inscription on its blade is a string that is particularly often encountered on a tape during Skelet 1 simulation.]] | [[File:Skeleton warrior.png|thumb|A skeleton warrior holding a sword. The runic inscription on its blade is a string that is particularly often encountered on a tape during Skelet 1 simulation.]] | ||
{{TM|1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC}}, called '''Skelet #1''', was one of [[Skelet's 43 holdouts]] and one of the last holdouts in [[BB(5)]]. It was eventually proven to be a [[Translated Cycler]] by Pavel Kropitz and Shawn Ligocki. It is one of the few TMs to have required an individual proof of non-halting in [[Coq-BB5]].<ref name="bbchallenge 2025">https://arxiv.org/pdf/2509.12337 Determination of the fifth Busy Beaver value</ref> | |||
The translated cycle has a period 8,468,569,863 and start step about <math>5.42 \times 10^{51}</math>.<ref>[https://www.sligocki.com/2023/03/13/skelet-1-infinite.html#stats Skelet #1 is infinite] Statistics.</ref> Both of these values are gigantic in comparison to the runtime of the [[5-state busy beaver winner]] which runs for a "mere" 47 million steps. | |||
== Behavior == | |||
The machine can be analyzed in terms of a number of blocks, one leftward head, and one rightward head.<ref>[https://www.sligocki.com/2023/03/13/skelet-1-infinite.html#tape-representation Skelet #1 is infinite] Tape representation.</ref> The blocks include base-4 digits and filler. As the simulation proceeds, digits occasionally collide and create "debris" that is later cleaned up. The head remains close to the right end of the tape, leaving behind patterns on the left end of the tape that are never visited again. In order to simulate this machine to translated cycling in a reasonable amount of time, two accelerations are needed: 1) counter acceleration, which involves the base-4 digits and filler, and 2) uni-cycle acceleration. Also, some common blocks of symbols can be repeated as many as 10<sup>19</sup> times and must be run-length encoded. Such an accelerated simulator can reach the translated cycle in several 10<sup>7</sup> simulator steps. | |||
== Preperiod == | == Preperiod == | ||
The exact preperiod (minimum cycle start start step) for Skelet 1 is not known, but @hipparcos computed it to be approximately 5418883027667422764169643414989497193809945789706483. This value is probably accurate to within about one period.<ref>[https://discord.com/channels/960643023006490684/1075378436404678707/1328263736686936066 @hipparcos 13 Jan 2025 Discord]</ref> | The exact preperiod (minimum cycle start start step) for Skelet 1 is not known, but @hipparcos computed it to be approximately 5418883027667422764169643414989497193809945789706483. This is an upper bound (by this point the TM is cycling). This value is probably accurate to within about one period.<ref>[https://discord.com/channels/960643023006490684/1075378436404678707/1328263736686936066 @hipparcos 13 Jan 2025 Discord]</ref> | ||
== See also == | |||
* [[Skelet 10]] | |||
* [[Skelet 17]] | |||
== References == | == References == | ||
| Line 10: | Line 19: | ||
== See Also == | == See Also == | ||
* https://www.sligocki.com/2023/02/25/skelet-1-wip.html | * [https://www.sligocki.com/2023/02/25/skelet-1-wip.html Skelet #1: What I Know]. 25 Feb 2023. Shawn Ligocki | ||
* https://www.sligocki.com/2023/02/27/skelet-1-halting-config.html | * [https://www.sligocki.com/2023/02/27/skelet-1-halting-config.html Skelet #1: A Halting Counter Config]. 27 Feb 2023. Shawn Ligocki | ||
* https://www.sligocki.com/2023/03/13/skelet-1-infinite.html | * [https://www.sligocki.com/2023/03/13/skelet-1-infinite.html Skelet #1 is infinite ... we think]. 13 Mar 2023. Shawn Ligocki | ||
[[Category: | * Simulation code by Pavel & Shawn: https://github.com/univerz/bbc/tree/no1 | ||
[[Category:BB(5)]] | |||
Latest revision as of 06:39, 15 October 2026
1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC (bbch), called Skelet #1, was one of Skelet's 43 holdouts and one of the last holdouts in BB(5). It was eventually proven to be a Translated Cycler by Pavel Kropitz and Shawn Ligocki. It is one of the few TMs to have required an individual proof of non-halting in Coq-BB5.[1]
The translated cycle has a period 8,468,569,863 and start step about .[2] Both of these values are gigantic in comparison to the runtime of the 5-state busy beaver winner which runs for a "mere" 47 million steps.
Behavior
The machine can be analyzed in terms of a number of blocks, one leftward head, and one rightward head.[3] The blocks include base-4 digits and filler. As the simulation proceeds, digits occasionally collide and create "debris" that is later cleaned up. The head remains close to the right end of the tape, leaving behind patterns on the left end of the tape that are never visited again. In order to simulate this machine to translated cycling in a reasonable amount of time, two accelerations are needed: 1) counter acceleration, which involves the base-4 digits and filler, and 2) uni-cycle acceleration. Also, some common blocks of symbols can be repeated as many as 1019 times and must be run-length encoded. Such an accelerated simulator can reach the translated cycle in several 107 simulator steps.
Preperiod
The exact preperiod (minimum cycle start start step) for Skelet 1 is not known, but @hipparcos computed it to be approximately 5418883027667422764169643414989497193809945789706483. This is an upper bound (by this point the TM is cycling). This value is probably accurate to within about one period.[4]
See also
References
- ↑ https://arxiv.org/pdf/2509.12337 Determination of the fifth Busy Beaver value
- ↑ Skelet #1 is infinite Statistics.
- ↑ Skelet #1 is infinite Tape representation.
- ↑ @hipparcos 13 Jan 2025 Discord
See Also
- Skelet #1: What I Know. 25 Feb 2023. Shawn Ligocki
- Skelet #1: A Halting Counter Config. 27 Feb 2023. Shawn Ligocki
- Skelet #1 is infinite ... we think. 13 Mar 2023. Shawn Ligocki
- Simulation code by Pavel & Shawn: https://github.com/univerz/bbc/tree/no1