Skelet #10: Double Fibonacci Counter
Skelet #10 is infinite. Unlike my recent posts for Skelet #34 and Skelet #1 this result appears to have previously been demonstrated by Dan Briggs.^{1} However, it’s behavior is quite intriguing, so I’d like to draw some attention to it.
Skelet #10 is a double binary counter, but with two twists:
 It counts using Fibonacci encoding.
 Proving it infinite requires demonstrating that the count on both sides is synchronized.
I believe this “synchronization” criterion is why CTL methods have not been able to prove it yet. And I think it’s a good candidate for an Irregular TM (TM that cannot be proven using CTL (Regular Language) methods).
The Machine
The TM I will be discussing here is Skelet #10 which he describes with the notation C1L A0L H1L C0L D0R A1L B1L E1R D1R E0R
. Converted into Tree Normal Form (TNF) and using Standard Text format this is:
1RB0RA_0LC1RA_1RE1LD_1LC0LD_0RB
0  1  

A  1RB  0RA 
B  0LC  1RA 
C  1RE  1LD 
D  1LC  0LD 
E  —  0RB 
It is TM #3,810,716 on bbchallenge.org.
For the rest of this article, I will use this TNF state naming.
Fibonacci Notation
Let me first define Fibonacci notation. Fibonacci notation is a placevalue notation like Binary notation, but instead of the nth place representing \(2^n\), it represents \(F_{n+2}\) (the \(n+2\)nd Fibonacci number).^{2} So, for example, consider the notation 10100
. In standard, bigendian binary notation this represents the number \(1 \cdot 2^4 + 1 \cdot 2^2 = 16 + 4 = 20\). In (bigendian) Fibonacci notation it represents the number \(1 \cdot F_{4+2} + 1 \cdot F_{2+2} = 8 + 3 = 11\).
Every natural number (nonnegative integer) can be represented in “at least” one way in Fibonacci notation. But unlike Binary notation, there can be two different Fibonacci notations for the same number. For example, both 11
and 100
represent the number 3!
Zeckendorf representation
However, it turns out that we can identify one “canonical” representation for every natural number by adding a single restriction: don’t allow any bit sequences to have any adjacent 1
s (i.e. don’t allow subsequence 11
). By Zeckendorf’s theorem this leaves a single unique representation for every natural number called the Zeckendorf representation.
Let me specifically define \(Z(n)\) to be the littleendian, Zeckendorf representation of \(n\). So \(Z(11) = 00101\). Furthermore, notice that adding trailing zeros does not change the representation, so really we can consider the Zeckendorf representation to have infinite 0
s to the right and so 00101
is sortof a shorthand for 001010000...
.
Zeckendorf Increment
Notice that since the Zeckendorf representation does not have any 11
s, every 1
must be followed by a 0
. So we can write any Zeckendorf representation as a sequence of 0
and 10
s. For our example 11 (00101
), that would look like 0 0 10 10
(note that I include one trailing 0
here).
What happens when we increment a number written in Zeckendorf representation? It turns out that there are some relatively simple rules for incrementing:
\[\begin{array}{ccrl} Z(n) & = & 0 & 10^k & 0 & w & \implies & Z(n+1) & = & 0^{2k} & 10 & w \\ Z(n) & = & 10 & 10^k & 0 & w & \implies & Z(n+1) & = & 0^{2k+1} & 10 & w \\ \end{array}\]Where \(10^k\) means k repetitions of 10
, \(0^k\) means k repetitions of 0
and \(w\) is an arbitrary (possibly empty) suffix of \(Z(n)\).^{3}
I leave proof of these as exercise to the reader. They follow directly from the facts that \(F_{n+2} = F_n + F_{n+1}\) and \(F_3 = F_2 + 1\).
Right Side Counter
We now have enough theory to describe the behavior of the right side counter. At the basic TM level, it obeys these rules:
\[\begin{array}{crl} \text{A>} & 0 & 10^k & 0 & \to & \text{<D} & 0^{2k} & 10 \\ \text{B>} & 10 & 10^k & 0 & \to & \text{<D} & 0^{2k+1} & 10 \\ \end{array}\]Do these look familiar? They are exactly the Zeckendorf increment rules! So we can restate these as:
\[\begin{array}{c} Z(n) = 0 \; w & \implies & \text{A>} & Z(n) & \to & \text{<D} & Z(n+1) \\ Z(n) = 1 \; w & \implies & \text{B>} & Z(n) & \to & \text{<D} & Z(n+1) \\ \end{array}\]Where by \(Z(n) = 0 \; w\) I mean that the leastsignificant bit in \(Z(n)\) is 0
.
Left Side Counter
Alas, the left side counter is not quite so easy to describe. In a way, we got very lucky that the right side counter used the exact same notation as our Zeckendorf representation!
For the left side counter, it is encoded with these differences:
 Different Symbols: Each
10
from the Zeckendorf representation is encoded as1010
on the tape, each0
from Zeckendorf is encoded as00
.  Reversed: The leastsignificant bit is now on the right side.
 The two leastsignificant (rightmost) tape symbols are omitted.
Formally, let’s define \(T(w)\) and \(L(n)\) by:
 For any \(w \in (010)^*\) (in other words, any valid Zeckendorf representation) and let \(\epsilon\) be the empty word, then \(T(w)\) is defined recursively as:
 And \(L(n)\) is defined as (where \(v \in (01)^*\) and \(a, b \in (01)\)):
So, \(T(w)\) reverses the order of \(w\) and applies the symbol transformation and \(L(n)\) takes that result and strips the leastsignificant (rightmost) 2 tape symbols. As an example:
 \(Z(11) = 0010100...\) which we split up as
0 0 10 10 0...
 Reversing and using new tape encoding we get \(T(Z(11))\) =
...00 1010 1010 00 00
 Finally, removing two leastsignificant tape symbols we get
...00 1010 1010 00
. So \(L(11) = ...001010101000\)
Let’s consider 3 cases based upon the 3 possible values for the 2 leastsignificant bits in \(Z(n)\):
\(Z(n)\)  \(T(Z(n))\)  \(L(n)\) 

\(00 \; w\)  \(T(w) \; 00 \; 00\)  \(T(w) \; 00\) 
\(0 \; 10^{k+1} \; 0 \; w\)  \(T(w) \; 00 \; 1010^{k+1} \; 00\)  \(T(w) \; 00 \; 10^{2k+1} \; 10\) 
\(10 \; 10^k \; 0 \; w\)  \(T(w) \; 00 \; 1010^{k+1}\)  \(T(w) \; 00 \; 10^{2k} \; 10\) 
And now let’s consider how increments affect this:
\(Z(n)\)  \(L(n)\)  \(Z(n+1)\)  \(L(n+1)\) 

\(00 \; w\)  \(T(w) \; 00\)  \(10 \; w\)  \(T(w) \; 10\) 
\(0 \; 10^{k+1} \; 0 \; w\)  \(T(w) \; 00 \; 10^{2k+1} \; 10\)  \(0^{2k+2} \; 10 \; w\)  \(T(w) \; 10 \; 10 \; 00^{2k+1}\) 
\(10 \; 10^k \; 0 \; w\)  \(T(w) \; 00 \; 10^{2k} \; 10\)  \(0^{2k+1} \; 10 \; w\)  \(T(w) \; 10 \; 10 \; 00^{2k}\) 
Now, consider the following base TM rules:
\[\begin{array}{c} & & 00 & \text{<D} & \to & & & 10 & \text{B>} \\ 00 & 10^k & 10 & \text{<D} & \to & 10 & 10 & 00^k & \text{A>} \\ \end{array}\]Aha, these look just like the \(L(n)\) and \(L(n+1)\) cases above! And so:
\[\begin{array}{c} Z(n) = 00 \; w & \implies & L(n) & \text{<D} & \to & L(n+1) & \text{B>} \\ Z(n) \ne 00 \; w & \implies & L(n) & \text{<D} & \to & L(n+1) & \text{A>} \\ \end{array}\]Where by \(Z(n) = 00 \; w\) I mean that the two leastsignificant bits in \(Z(n)\) are 00
and by \(Z(n) \ne 00 \; w\) I mean the opposite case.
Complete Behavior
Bringing all the Fibonacci counter rules together we have:
\[\begin{array}{c} Z(n) = 0 \; w & \implies & \text{A>} & Z(n) & \to & \text{<D} & Z(n+1) \\ Z(n) = 1 \; w & \implies & \text{B>} & Z(n) & \to & \text{<D} & Z(n+1) \\ \end{array}\] \[\begin{array}{c} Z(n) = 00 \; w & \implies & L(n) & \text{<D} & \to & L(n+1) & \text{B>} \\ Z(n) \ne 00 \; w & \implies & L(n) & \text{<D} & \to & L(n+1) & \text{A>} \\ \end{array}\]Additionally, the TM starts in configuration \(L(0) \;\; \text{A>} \;\; Z(0)\). The only complexity remaining is to prove that the TM is in the correct A>
or B>
config at the right time so that these rules can be applied forever.
Theorem: Let \(D(n) = L(n) \;\; \text{<D} \;\; Z(n+1)\), then \(D(n) \to D(n+1)\)
Proof: Let us again consider the 3 cases for \(Z(n)\):
 If \(Z(n) = 00 \; w\), then \(Z(n+1) = 10 \; w\) and so we have:
 If \(Z(n) = 0 \; 10^{k+1} \; 0 \; w\), then \(Z(n+1) = 0^{2k+2} \; 10 \; w\) and so we have:
 If \(Z(n) = 10 \; 10^k \; 0 \; w\), then \(Z(n+1) = 0^{2k+1} \; 10 \; w\) and so we have:
QED
The crux here is basically the fact that \(Z(n+1)\) starts with 1
if and only if \(Z(n)\) starts with 00
.
And finally, we can see that the TM starts in config \(L(0) \;\; \text{A>} \;\; Z(0)\) which proceeds to \(L(0) \;\; \text{<D} \;\; Z(1) = D(0)\) and thus, this TM is infinite.
An Irregular Machine?
Note: A few days after I posted this article, @Iijil shared an elegant proof for a (different) Irregular TM.
The proof that this TM is infinite in the last section depended on one specific detail: That the Fibonacci Counters on the left and right were synchronized (specifically that the right count was 1 ahead of the left count). This might be why CTL deciders have not been able to prove this machine yet.
I wrote about the theory behind CTL last summer and since then, there has been significant improvement among the bbchallenge.org community to develop the idea into extremely effective deciders. But let me restate the basic idea here:
A Closed Set proof consists of defining a set \(C\) of TM configurations and proving the following properties:
 This TM enters the set: At some step, the TM is in a config \(c \in C\).
 The set is closed under TM step: For all \(c \in C\) there exists some number of steps \(s \ge 1\) such that \(c \to d\) in \(s\) steps and \(d \in C\).
 No configuration in \(C\) is a halting configuration.
For example, my theorem above is a Closed Set proof (In fact, every proof I have ever seen of TMs being infinite is a Closed Set proof. This concept is very broad!).
A CTL proof is a Closed Set proof where the set \(C\) is a Regular Language (defined via Regular Expression or a FiniteState Machine or another equivalent method) and \(s = 1\) in the closure rule above (for all \(c \in C\) and \(c \to d\) in 1 step, then \(d \in C\)).
Regular Languages have turned out to be extremely powerful in constructing Closed Set proofs. But they have (at least theoretical) limitations. One open question that has come up again and again is: What is an example of an infinite TM which cannot be proven infinite using CTL (because there does not exist any regular language \(C\) with the Closed Set properties listed above). I will call such a TM Irregular … because, you know, it’s not Regular :)
I conjecture that Skelet #10 is an Irregular TM, but I don’t yet have a proof. But here are some facts that make me think it is:
 The set \(\{L(n) \;\; \text{<D} \;\; Z(n+1)\}\) used in my proof is not a regular language. This can be proven using the Pumping Lemma.
 All configurations \(L(n) \;\; \text{<D} \;\; Z(m)\) with \(m \ne n+1\) eventually diverge from the rules listed above (specifically, eventually they end up in a config like
0 A> 10
or0 B> 0
).  Many of these halt:
0 B> 0 > Halt
in 3 steps,0 A> 10 10 ... > Halt
in a longer series of steps. However, for0 A> 10 0 ...
it’s a little less clear what happens.
So, in order to prove that this TM is Irregular, I think you’ll basically have to prove that any closed regular language \(C \supseteq \{L(n) \;\; \text{<D} \;\; Z(n+1)\}\) must also contain some halting configurations (like the ones I’ve listed).
Related Articles
This article is part of a series studying Skelet TMs:

Skelet #10: Double Fibonacci Counter
Footnotes

You can find his explanation on github although I haven’t been able to understand the details myself. ↩

I start this Fibonacci sequence with \(F_2 = 1\) and \(F_3 = 2\) so that each Fibonacci number is distinct. ↩

Note: these rules are similar to the Binary increment rule: \(B(n) = 1^n 0 w \implies B(n+1) = 0^n 1 w\) ↩