Skelet 10
1LC0LA_---0LC_0RD1LA_1LB1RE_1RD0RE (bbch), called Skelet #10, was one of Skelet's 43 holdouts and one of the last holdouts in BB(5). It is a double fibonacci counter. It is one of the few TMs to have required an individual proof of non-halting in Coq-BB5.[1]
Behavior
Skelet 10 implements two base fibonacci counters, one on the right tape side and one on the left tape side. The TM halts if these counters become desynchronised.[1] The right side counter can be described by the following rules:[2]
A> 0 10^k 0 --> <D 0^2k 10 B> 10 10^k 0 --> <D 0^2k+1 10
These rules are equivalent to the Zeckendorf increment rules:[2]
Z(n) = 0 10^k 0 w ==> Z(n+1) = 0^2k 10 w Z(n) = 10 10^k 0 w =0> Z(n+1) = 0^2k+1 10 w Where Z(n) represents n in the little-endian (least significant digit is on the left) representation of Zeckendorf notation.
and can be restated as:[2]
Z(n) = 0 w ==> A> Z(n) --> <D Z(n+1) Z(n) = 1 w ==> B> Z(n) --> <D Z(n+1) Where Z(n) = 0 w means that the least-significant bit in Z(n) is 0.
The left side counter encodes base fibonacci differently and is also reversed, with the least-significant digit being on the right. It can be described by the following rules:[2]
00 <D --> 10 B> 00 10^k 00 <D --> 10 10 00^k A>
See also
References
- ↑ 1.0 1.1 https://arxiv.org/pdf/2509.12337 Determination of the fifth Busy Beaver value
- ↑ 2.0 2.1 2.2 2.3 https://www.sligocki.com/2023/03/14/skelet-10.html