Skelet 10: Difference between revisions
big-endian |
Added cases for least-significant digits |
||
| Line 2: | Line 2: | ||
{{TM|1LC0LA_---0LC_0RD1LA_1LB1RE_1RD0RE}}, 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]].<ref name="bbchallenge 2025">https://arxiv.org/pdf/2509.12337 Determination of the fifth Busy Beaver value</ref> | {{TM|1LC0LA_---0LC_0RD1LA_1LB1RE_1RD0RE}}, 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]].<ref name="bbchallenge 2025">https://arxiv.org/pdf/2509.12337 Determination of the fifth Busy Beaver value</ref> | ||
== | == [https://www.sligocki.com/2023/03/14/skelet-10.html Analysis] by [[User:Sligocki|Shawn Ligocki]] == | ||
Skelet 10 implements two [https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem base fibonacci] counters, one on the right tape side and one on the left tape side. The TM halts if these counters become desynchronised.<ref name="bbchallenge 2025"/> The right side counter can be described by the following rules:<ref name="Sligocki">https://www.sligocki.com/2023/03/14/skelet-10.html</ref> | Skelet 10 implements two [https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem base fibonacci] counters, one on the right tape side and one on the left tape side. The TM halts if these counters become desynchronised.<ref name="bbchallenge 2025"/> The right side counter can be described by the following rules:<ref name="Sligocki">https://www.sligocki.com/2023/03/14/skelet-10.html</ref> | ||
| Line 34: | Line 34: | ||
where v is any valid Zeckendorf expression. | where v is any valid Zeckendorf expression. | ||
--> This removes the two least-significant tape symbols. | --> This removes the two least-significant tape symbols. | ||
</pre> | |||
There are now 3 possible cases for 3 possible values of the two least-significant digits of the left counter: | |||
<pre> | |||
Z(n) = 00 w --> T(Z(n)) = T(w) 00 00 --> L(n) = T(w) 00 | |||
Z(n) = 0 10^k+1 0 w --> T(Z(n)) = T(w) 00 10 1010^k+1 00 --> L(n) = T(w) 00 10^2k+1 10 | |||
Z(n) = 10 10^k 0 w --> T(Z(n)) = T(w) 00 1010^k+1 --> L(n) = T(w) 00 10^2k 10 | |||
</pre> | </pre> | ||
Revision as of 14:40, 21 February 2026
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]
Analysis by Shawn Ligocki
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 to big-endian (least significant digit is on the right). The two least-significant symbols are also omitted. These differences can be described using the following definitions:[2]
T(0w) = T(w)00 T(10w) = T(w)1010 T(empty) = empty where w is any valid Zeckendorf expression. --> This encodes the Zeckendorf representations in a way consistent with the left fibonacci counter by encoding 10 as 1010 and 0 as 00. This also reverses the order of the Zeckendorf representation to big-endian. L(n) is defined in the following way: T(Z(n)) = v ab ==> L(n) = v where v is any valid Zeckendorf expression. --> This removes the two least-significant tape symbols.
There are now 3 possible cases for 3 possible values of the two least-significant digits of the left counter:
Z(n) = 00 w --> T(Z(n)) = T(w) 00 00 --> L(n) = T(w) 00 Z(n) = 0 10^k+1 0 w --> T(Z(n)) = T(w) 00 10 1010^k+1 00 --> L(n) = T(w) 00 10^2k+1 10 Z(n) = 10 10^k 0 w --> T(Z(n)) = T(w) 00 1010^k+1 --> L(n) = T(w) 00 10^2k 10
The TM follows these rules on the left:[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 2.4 https://www.sligocki.com/2023/03/14/skelet-10.html