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:

  1. It counts using Fibonacci encoding.
  2. 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 place-value notation like Binary notation, but instead of the n-th 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, big-endian binary notation this represents the number \(1 \cdot 2^4 + 1 \cdot 2^2 = 16 + 4 = 20\). In (big-endian) Fibonacci notation it represents the number \(1 \cdot F_{4+2} + 1 \cdot F_{2+2} = 8 + 3 = 11\).

Every natural number (non-negative 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 1s (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 little-endian, 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 0s to the right and so 00101 is sort-of a shorthand for 001010000....

Zeckendorf Increment

Notice that since the Zeckendorf representation does not have any 11s, every 1 must be followed by a 0. So we can write any Zeckendorf representation as a sequence of 0 and 10s. 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 least-significant 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 as 1010 on the tape, each 0 from Zeckendorf is encoded as 00.
  • Reversed: The least-significant bit is now on the right side.
  • The two least-significant (rightmost) tape symbols are omitted.

Formally, let’s define \(T(w)\) and \(L(n)\) by:

  • For any \(w \in (0|10)^*\) (in other words, any valid Zeckendorf representation) and let \(\epsilon\) be the empty word, then \(T(w)\) is defined recursively as:
\[\begin{array}{l} T(0w) & = & T(w) 00 \\ T(10w) & = & T(w) 1010 \\ T(\epsilon) & = & \epsilon \\ \end{array}\]
  • And \(L(n)\) is defined as (where \(v \in (0|1)^*\) and \(a, b \in (0|1)\)):
\[T(Z(n)) = v \; ab \implies L(n) = v\]

So, \(T(w)\) reverses the order of \(w\) and applies the symbol transformation and \(L(n)\) takes that result and strips the least-significant (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 least-significant 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 least-significant 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 least-significant 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:
\[\begin{array}{l} L(n) & \text{<D } & Z(n+1) & \to \\ L(n+1) & \text{ B>} & Z(n+1) & \to \\ L(n+1) & \text{<D } & Z(n+2) \\ \end{array}\]
  • If \(Z(n) = 0 \; 10^{k+1} \; 0 \; w\), then \(Z(n+1) = 0^{2k+2} \; 10 \; w\) and so we have:
\[\begin{array}{l} L(n) & \text{<D } & Z(n+1) & \to \\ L(n+1) & \text{ A>} & Z(n+1) & \to \\ L(n+1) & \text{<D } & Z(n+2) \\ \end{array}\]
  • If \(Z(n) = 10 \; 10^k \; 0 \; w\), then \(Z(n+1) = 0^{2k+1} \; 10 \; w\) and so we have:
\[\begin{array}{l} L(n) & \text{<D } & Z(n+1) & \to \\ L(n+1) & \text{ A>} & Z(n+1) & \to \\ L(n+1) & \text{<D } & Z(n+2) \\ \end{array}\]

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 Finite-State 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 or 0 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, for 0 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).

This article is part of a series studying Skelet TMs:

  1. Skelet #34 is Infinite

  2. Shift Overflow Counters

  3. Skelet #1: What I Know

  4. Skelet #1: A Halting Counter Config

  5. Skelet #1 is infinite … we think

  6. Skelet #10: Double Fibonacci Counter

Footnotes

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

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

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