The Xigxag Automaton

Xigxag is a simple automaton which exhibits exponential growth almost everywhere. In other words, there are only a finite number of initial configurations that do not blow up exponentially in size.

Definition

A Xigxag configuration is a string over the alphabet {<, >}*. So, for example, <<>> is a Xigxag configuration. When there is no danger of ambiguity, I'll refer to these simply as configurations in this document.

Like all automata, there is a binary relation between Xigxag configurations that describes how Xigxag "runs", which I'll call the Xigxag transition relation. The following procedure describes how the next-configuration t of a given configuration s can be obtained from s.

For each symbol k in s, such that s = lkr where l and r are strings (substrings of s),

Note that order matters in the above procedure. In Xigxag, s is examined left-to-right and t is likewise constructed left-to-right. Variations could be denoted with subscripts like Xigxag_LR to indicate that t is rather constructed right-to-left. However, I won't pursue such variations here.

A Xigxag execution sequence, or simply a run, for a given initial-configuration s is the sequence of configurations starting with s and closed under successive applications of the transition relation. Every execution sequences comprises a countably infinite number of configurations -- that is, runs never stop. They may, however, be ultimately periodic -- that is, they may reach some configuration to which they always return (a "fixed point.") But, as I'll attempt to show later, the number of initial configurations that lead to this is finite (and in fact, pretty small.)

Example

><<

<<>><

Continuing in this vein, the execution sequence for this initial configuration is

><<
<<>><
<><<<<>>
<<<<>><><><<><<<><<<>
...

Investigation

Sure, it's simple, but I find Xigxag moderately interesting -- interesting enough to devote this section to proving the following property: Xigxag has exponential growth almost everywhere.

(Gasp! Mathematical rigour, in an esolang! Say it isn't so! Don't worry, I'll try to be gentle. Anyway, you can just skip it if you don't dig proofs.)

To show this, I'm going to split the theorem into two parts: Xigxag has growth almost everywhere, and the magnitude of that growth is always Ω(2ⁿ) (where Ω(X) denotes a lower bound on the order of X.) And each of these will be split into several lemmas. But first, we need a couple of more definitions, just to make sure we're not relying too much on intuition.

A configuration s exhibits growth if the length of its next-configuration t is strictly greater, i.e. if |t| > |s|. We call the value |t| - |s| the expansion of s. The configuration of some length n that has the least expansion of any configuration of length n we call the minimal expander of length n.

The centre of a configuration, for configurations of odd length, is the symbol which has an equal number of symbols on either side of it, and for configurations of even length, is the gap between symbols which has an equal number of symbols on either side of it.

In addition, this minimal expander of length n is unique (up to the symbol represented by x).

Proof: For any symbol left of centre, there will be more symbols on its right than on its left. Therefore if some symbol left of centre is a >, more symbols will be copied into the next-configuration than if it were a <. So in a minimal expander, this symbol must be a <. A mirror-image argument applies for symbols right of centre. Since there is only one choice for these symbols, the minimal expander is unique as well. The symbol at the centre (which only exists when n is odd) is inconsequential; since there are an equal number of symbols on either side of it, changing it will not affect the expansion. QED

Lemma 2a. If some configuration s exhibits growth and s contains at least one <, then the configuration <s also exhibits growth.

Proof: Say s has length n and the next-configuration of s has length n + m for some positive m. Then the next-configuration of <s has length of at least n + m because every symbol in s still has at least as many symbols on either side of it and is thus still copying substrings into the next-configuration that are at least as long. In addition, one of the symbols in s is a <; this < will "see" the new < prefix and will copy it as well; so the next-configuration of <s has length of at least n + m + 1. Therefore <s exhibits growth. QED

Lemma 2b. If some configuration s exhibits growth and s contains at least one >, then the configuration s> also exhibits growth.

Lemma 3. If some minimal expander of length n exhibits growth, then so does the minimal expander of length n + 1.

Proof: Given the minimal expander s of length n, we can form a minimal expander of length n + 1 by:

These cases can easily be checked against Lemma 1. Further, from Lemmas 2a and 2b we know that appending > or prefixing < to a configuration that exhibits growth will produce a new configuration that also exhibits growth. Thus, if some minimal expander of length n exhibits growth, then so does the minimal expander of length n + 1. QED

Lemma 4. All but a finite number of initial Xigxag configurations exhibit growth.

Proof: By induction. Note that the Xigxag configuration <<<<>>>> is a minimal expander of length 8 (by Lemma 1.) Note also that it has a next-configuration of <<<<<<>>>>>>, which has a length of 12. Clearly 12 > 8, thus it exhibits growth.

Also, we know by Lemma 3 that if a minimal configuration of length n exhibits growth, so does the minimal expander of length n + 1.

So, since the minimal expander of length 8 exhibits growth, and since if a minimal expander of length n exhibits growth so does a minimal expander of length n + 1, all minimal expanders of length 8 or greater exhibit growth.

In addition, if a minimal expander of length n exhibits growth, then all configurations of length n must exhibit growth (since a minimal expander expands the least of all configurations of its size.) Therefore all Xigxag configurations of length 8 or greater exhibit growth, and the only Xigxag configurations that do not exhibit growth must have length less than 8. There are clearly only a finite number of such configurations. QED

Lemma 5. For all integers n ≥ 1, 4·2ⁿ⁺¹ ≥ 6·2^n-1. (The relevance of this will become apparent later.)

Proof: By induction. For n = 1, 4·2ⁿ⁺¹ = 4·2² = 16 ≥ 6·2^n-1 = 6·2¹ = 12. So the base case is proved.

Now we wish to show 4·2ⁿ⁺² ≥ 6·2ⁿ. Divide both sides by 2 to obtain 2·2ⁿ⁺² ≥ 6·2^n-1. But note that 2·2ⁿ⁺² = 4·2ⁿ⁺¹, so the expression can be restated 4·2ⁿ⁺¹ ≥ 6·2^n-1. But this is exactly our inductive hypothesis! So the inductive step is proved, proving the lemma. QED

Lemma 6. The length of the next-configuration of a minimal expander of length n is Ω(2ⁿ).

Proof: Let's tackle this by finding a closed-form expression T(n) for the length of the next-configuration of a given minimal expander of length n, where n is even.

(Note that we haven't shown that the next-configuration of a minimal expander is another minimal expander. In fact this is true, but we don't have to show it because, from the definition of minimal expanders, we know that any next-configuration of a minimal expander will have at least as much expansion as a minimal expander would. That's also what lets us phrase the result in terms of a lower bound using Ω-notation.)

First, we find a recurrence formula. From Lemma 1, observe that the left half of a minimal expander consists of n/2 < symbols. The first < will not "see" any other symbols; the second will "see" exactly one other symbol (the first <); the third will "see" two symbols, and so forth. The total number of symbols "seen" by the left half will be the sum of the integers between 1 and n/2 - 1. The closed form for such a sequence is m(m + 1) / 2; in our case this works out to (n/2 - 1)(n/2) / 2. A mirror-image argument applies to what the > symbols "see" in the other half of the string, so we can double this to obtain (n/2 - 1)(n/2), and multiply this out to obtain n²/4 - n/2. So our recurrence formula looks like:

T(2) = T(1)²/4 - T(1)/2 = 8²/4 - 8/2 = 64/4 - 4 = 16 - 4 = 12, so this coincides with what we already saw in Lemma 4.

Now we use the "substitution method": we guess that the closed form of this recurrence is greater than c2ⁿ for some constant c, and we substitute this into the recurrence formula, checking to confirm that it holds. (For more on this method, see, e.g. section 4.1 of Introduction to Algorithms, 2nd ed., by Cormen, Leiserson, Rivest, and Stein.)

So T(n) ≥ c2ⁿ holds provided we can find some c that satisfies both T(1) = 8 and c2ⁿ⁺¹ ≥ (c(c - 1)/2)2^n-1 for all n ≥ 1. First we examine T(1):

So let c = 4, and note that (c(c - 1)/2) = 6. Indeed, 4·2ⁿ⁺¹ ≥ 6·2^n-1 is true for all n ≥ 1 by Lemma 5. So the closed form holds. QED

In fact, it seems to me that there's an awful lot of wiggle room between 4·2ⁿ⁺¹ and 6·2^n-1, so I'll wager a guess that it's not ω(2ⁿ) (that is, that the bound I've given of 2ⁿ is not tight, and can be improved upon.)

Also, I chose 8 as the base case of the induction to keep things simple. In fact, after only five generations, the length-4 initial configuration <>>< balloons into a configuration of length 1,267,174. I think all length-7 configurations grow exponentially as well, but there are configurations of length 6 that are stable (namely <<<>>>.)

Is it Turing-complete?

Oh, I seriously doubt it. But then, I seriously doubt a lot of things. I doubt the Kolakoski sequence is (asymptotically speaking) unevenly distributed; I doubt that there's some initial value from which the Collatz sequence fails to terminate; I doubt that P = NP. These doubts are founded on intuition, however, not proof, and intuition has led me astray in the past.

So, how would one go about confirming my intuition and proving that Xigxag isn't Turing-complete?

For some languages, like beta-Juliet or SMETANA, we can say that, because every program gives rise to only a finite number of possible internal configurations during a run (no matter its input), and because Turing machines can take on an infinite number of internal configurations during a run, the language can't possibly be Turing-complete. Alas, we can't say that for Xigxag, because almost all Xigxag "programs" (initial configurations) give rise to a countably infinite sequence of different configurations during an execution sequence.

The fact that Xigxag execution never "halts" is also not helpful -- the same is true for all cellular automata, and this hurdle is usually overcome by attaching a "termination predicate" to the system. That is, if some configuration meets some condition (e.g. contains some substring,) then we consider the system to have halted.

From this, we can formulate the inclusion problem for Xigxag: given a particular string s over the alphabet {<, >}*, does there exist a Xigxag execution sequence where s occurs as a substring in one of the configurations, but not in the initial configuration? I suspect that if one could show that this problem is decidable -- or, stronger, if one could give an algorithm for determining what that initial configuration is -- that would imply that Xigxag is not Turing-complete.

Another approach one could take is to find a very small Turing machine which simulates the Xigxag automaton and show that it is too small to be a universal Turing machine. I haven't tried this in detail, but I'm skeptical because Xigxag has a lot of "nonlocal motion" (symbols that cause faraway substrings to be copied to new places that would be, on a single-tape machine, also faraway) which would seem to entail a lot of states/symbols.

Background and Implementation

I apparently came up with this automaton, and wrote a buggy Perl implementation of it, in 2001. I also apparently didn't find it very interesting at the time, and shelved it. I rediscovered my Perl script in 2007, debugged it, and released it into the public domain. At the same time, I christened the automaton that it implements Xigxag, and went about proving (as you may have read above) that it exhibits exponential growth almost everywhere.