Skelet 1

Unsolved problem:

What is the exact cycle preperiod of Skelet 1?

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.

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.

The translated cycle has a period 8,468,569,863 and start step about $5.42\times 10^{51}$. 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 hard. 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¹⁹ times and must be run-length encoded. Such an accelerated simulator can reach the translated cycle in several 10⁷ 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.

See also

• Skelet 10
• Skelet 17

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