Talk:Xigxag

This one's pretty cool. I'll have to make an interpreter in brainfuck, right now. :D --Keymaker 10:25, 2 November 2007 (UTC)

Turing completeness?

My intuition agrees with the author's, that this language is not Turing complete; but it's fun to study anyway. (It would've been cute to have computation embedded in bracket-strings expanding without bound.) The main reason I think it's not universal is that there seems to be no provision for a "conditional act"; i.e., it's missing the kind of atomic action needed to get something equivalent to a while-loop. (A vaguely similar language is Self-BCT described on my webpage for BCT, which does have conditional actions -- namely 1x appends x iff the leftmost bit is 1 -- so I think in that case there's a good chance of universality.) For fun, here's XigXag expressed as a Post canonical system:

Alphabet: {[, ], <, >}
Initial word: [W]
Production rules:
    X[>Y]Z → X>[Y]ZY     (1)
    X[<Y]Z → X<[Y]ZX     (2)
      X[]Z → [Z]         (3)
where W, X, Y, Z are in {<, >}*.
 
E.g. derivation of next-configuration <><<<<>> from configuration <<>><:
[<<>><]           initial word
<[<>><]           by (2)
<<[>><]<          by (2)
<<>[><]<><        by (1)
<<>>[<]<><<       by (1)
<<>><[]<><<<<>>   by (2)
[<><<<<>>]        by (3)
...

--r.e.s. (Talk) 18:50, 3 November 2007 (UTC)

I'm pretty sure I have a proof that Xigxag is not Turing-complete. Take any two Xigxag configurations a and b. The problem of determining whether or not there is a series of Xigxag transitions that goes from a to b is decidable. (For any form ≥7 symbols long, just keep applying the transition relation to a: if you get b, there is such a series, but if you get a form longer than b, there isn't. The number of forms <7 symbols long is finite, so construct a lookup table and use that.) On the other hand, the problem of determining whether or not there is a series of Turing machine transitions between two arbitrary Turing machine configurations is undecidable (it can be reduced to the Halting Problem.) So, unless I'm missing something, Xigxag must not be Turing-complete. --Chris Pressey 03:19, 12 November 2007 (UTC)

At first glance I thought you'd nailed it, but the following seems to show otherwise: Consider any UTM (say U), with two-way infinite tape, that never visits cells to the left of the starting cell; then another UTM (say V) exists that simulates U and in addition appends two dummy symbols to the left side of the data during each & every simulated transition of U. Now V is equivalent to U but the "data portion" of its tape is of strictly-increasing length; consequently, the configurations of V are of strictly increasing length when each is written as a string of the form AqsB, where q is the current state of the controller, s the currently scanned symbol, and A/B is the finite "data portion" of the tape to the left/right of the scanned cell. So it seems that for the universal machine V, the problem of whether starting-configuration a evolves into the exact string b is decidable, for the reasons you outlined. A problem that's undecidable for V is this (the "substring derivation" problem): for arbitrary configuration a and string b, does a computation starting in configuration a evolve into a configuration that contains b as a substring. This is undecidable because it would otherwise solve the halting problem, as halting occurs iff a certain substring — the q of a halting state — appears in the configuration. I think your proof would be repaired if it showed that the "substring derivation" problem in Xigxag is decidable. (In any case, my intuition still agrees with yours, that Xigxag is not universal.) --r.e.s. (Talk) 19:01, 12 November 2007 (UTC)

Ah, indeed, I believe you are correct. I should've known it was too simple (especially since I worked out something similar regarding substring inclusion in the Kolakoski sequence a while ago.) As I recall, that problem was exceedingly difficult, in that it "smelled" like Post's Correspondence Problem - you don't know where the parts of the substring might've come from. Maybe Xigxag's super-exponential growth could be used in some sort of pumping argument, though. --Chris Pressey

Periodic Patterns

Considering Chris Pressey's proof that a pattern which does not follow exponential growth must be 7 characters long or less, I asked myself if there were any periodical patterns. I found the obvious

<<<
>>>
<<<>>>

Are there any other periodical patterns? --Boily 02:45, 4 November 2007 (UTC)

Searching by program I found only two more: the empty string and <><>. --Ørjan 07:33, 4 November 2007 (UTC)

Haven't found any others, either, and seems there likely aren't, Oerjan having gone through them with a program. I'll add these to the article! --Keymaker 09:58, 4 November 2007 (UTC)

By the way the program (slightly cleaned up) is (in Haskell):

import Data.List
import Control.Monad (replicateM)

xigxag s = [c |
    (b,x:a) <- zip (inits s) (tails s),
    c <- case x of '<' -> b; '>' -> a; _ -> error "illegal character" ]

patterns n = replicateM n "<>"

main = print [(p,p') |
    p <- concatMap patterns [1..7],
    let p' = iterate xigxag p !! 3,
    length p' `elem` [1..7] ]

--Ørjan 20:19, 4 November 2007 (UTC)

I was planning to survey the stable forms, but never got around to it... I think I was aware of most of them, except for <><> which I don't remember seeing before. Cool! --Chris Pressey 03:12, 12 November 2007 (UTC)

Proof of infinite growth

The documentation page gives a proof that all sequences of length 8 or more exhibit growth. In fact, it can be proven more simply that all sequences of length 7 or more do.

Let X(n) be the minimum length of the next generation for sequences of length n.

First consider the case where n is even:

Let n = 2k.

The symbols in the sequence generate at least 0, 1, 2, ..., k−2, k−1, k−1, k−2, ..., 2, 1, 0 symbols respectively in the next generation, giving

X(2k) = 2 ∑_r=0^k−1 r = (k−1)k.

If k ≥ 4, i.e. n ≥ 8, then

k−1 ≥ 3

⇒ X(2k) = (k−1)k ≥ 3k > 2k.

Now consider the case where n is odd:

Let n = 2k+1.

The symbols respectively generate at least 0, 1, 2, ..., k−1, k, k−1, ..., 2, 1, 0 symbols in the next generation, so

X(2k+1) = ∑_r=0^k r + ∑_r=0^k−1 r = k².

If k ≥ 3, i.e. n ≥ 7, then

X(2k+1) = k² ≥ 3k > 2k+1.

It can also be seen from this that X(6) = 6, therefore a sequence of length 6 will either remain the same length or grow. -- Smjg 15:48, 10 November 2007 (UTC)

Super-exponential growth

If I haven't miscalculated, [Smjg's proof] implies that in t steps an initial string of length n >= 7 acquires a length at of least 6*(n/6)^2t, which is actually super-exponential growth. E.g., for n = 7, the t-step length is at least 6*(7/6)^2t, and for n = 12 the t-step length is at least 6*2^2t, etc.--r.e.s. (Talk) 03:39, 11 November 2007 (UTC)

I'm not sure. The sequence <<<>>>>, which has the shortest next generation of all 7-symbol sequences, grows as 9, 18, 108, 5463, 14903073, which exceeds the lower bound formula that you've worked out. But I don't know whether this sequence leads to the shortest sequences for high values of t. -- Smjg 17:37, 11 November 2007 (UTC)

It's a lower bound, so of course it may be exceeded (that's its purpose). This lower bound, which I think is valid, is a super-exponential function — so the fact that it can only be equalled or exceeded shows that the growth-rate exceeds the exponential rate cited in the article. --r.e.s. (Talk) 18:34, 11 November 2007 (UTC)

PS: For anyone not familiar with the definition of the class of functions called super-exponential, there's a summary at http://online.mq.edu.au/pub/COMP333/Lecture/333_week1.pdf (see the sections "Hierarchy of functions" (1-3)). A function f(t) is in this class iff it "grows faster" than every exponential function; for this, I think it's necessary and sufficient that for any integer b >= 2, (b^t)/f(t) → 0 as t → oo. --r.e.s. (Talk) 19:01, 11 November 2007 (UTC)

Here are the details on the super-exponential growth rate ...

Smjg's proof (above) shows that any string of length n > 6 grows in one step to a length of at least

((n-1)/2)² if n is odd

(n/2)(n/2-1) if n is even.

Now for n > 6,

((n-1)/2)² > (n/2)(n/2-1) > n²/6,

so the growth in length proceeds as follows:

step   strict lower bound on length for n > 6

----    ---------------------------------------

0      n

1      n²/6 = 6 (n/6)²

2      ((n²/6)²)/6 = 6 (n/6)²²

3      ((6 (n/6)²²)²)/6 = 6 (n/6)²³

...

t      6 (n/6)^2t

...

Thus, for any integer b > 1, letting c = log_b(n/6) (note c > 0 for n > 6), gives

(b^t/6) / (n/6)^2t

= (1/6) b^{t - c2t}

→ 0 as t → oo,

so it follows that if a string initially has length n > 6, its length on step t is a super-exponential function of t. --(this comment by R.e.s. at 22:53, 11 November 2007 UTC; please sign your comments with ~~~~)

Yes, I see now and agree with your calculations. -- Smjg 13:57, 12 November 2007 (UTC)

We may also note that a string of length n grows in t steps to at most length n^2t, so the upper bound is of the same form as the lower one, apart from a couple of constant multipliers. --Ørjan 20:36, 12 November 2007 (UTC)