User:Hipparcos/Longitudinal analysis

Longitudinal analysis refers to ways of analyzing Turing machines in which the effect of the head on the tape is computed not necessarily in chronological order, but rather in "spatial" order, over successive sections of the tape. Unlike in the normal forward simulation of a Turing machine, in longitudinal analysis, there are multiple heads present at once. Sometimes, in analyzing TMs we talk about the effects of the head visiting a certain portion of the tape a certain number of times; longitudinal analysis provides a way of thinking about such situations. A major limitation of longitudinal analysis is that you must predict the state when the head returns to a given point on the tape; this limits the types of TMs that this method is applicable to. Different practitioners of longitudinal analysis have different notations and practices; in this article, I mostly follow dyuan's example, using the notation of inverse heads and discussing block analysis.

What is an inverse head?!

Recall that according to directed head notation, we can write the configuration of a Turing machine as something like 100 A> 1101. We think of the head as being "in between" tape symbols. In this example, the head has written a 0 on its left, and is traveling to the right. Soon it will read the 1 to its right, but not yet. (An alternative interpretation is that the head has already reached the next tape symbol. The arrow points at the symbol that the read/write head is currently located and about to read, and also points in the direction that the head has traveled from the previous step to the current step.) Inverse heads are a kind of extension to directed head notation. Starting from any given configuration, we can create a pair of a regular head and its inverse head. For example:

100 A> 1101
100 <B <B^-1 A> 1101

This inverse head <B^-1 is a prediction. Specifically, we are predicting that after the head A> continues to travel to the right, if and when it returns back to this spot, it will return as a <B. At that point, it can cancel out with the inverse head <B^-1. (Technically, we are also allowed to move the <B that we have created, but I choose to only move the A> for now.) We hope to see something like this:

100 <B <B^-1 A> 1101 (other symbols)
100 <B <B^-1 0110 C> (other symbols)
...a bunch of steps later...
100 <B <B^-1 0110 <D (other symbols)
100 <B <B^-1 <B 0011 (other symbols)
100 <B 0011 (other symbols)

(The symbols and states are just for illustrative purposes and are arbitrary.)

However, if the head comes back as some different state, then our analysis is invalid!

100 <B <B^-1 A> 1101 (other symbols)
...a bunch of steps later...
100 <B <B^-1 <C 0011 (other symbols)
      (ka-boom!)

We should have predicted the correct head. Fortunately for us, for some TMs, this is easy to do.

Another thing about inverse heads: when I do longitudinal analysis, I never move an inverse head by itself. This would amount to making another prediction about the forward simulation of the TM, which is difficult to reason about. I only create and destroy matching pairs of head and inverse head, and I move normal heads.

Longitudinal heads

Now consider what we can achieve if we pair a normal head traveling in one direction with an inverse head traveling in the opposite direction. Such a construction is so common that in the context of longitudinal analysis, we often refer to it as just "head". For a simple example, consider the binary counter 1RB---_1LC1RB_0RB0LC. If you look at the simulation of this TM, you'll see that the head going right is always B>, and the head going left is always <C.

The following four rules are commonly applied:

B> 0 -> <C 1
B> 1 -> 1 B>
0 <C -> 0 B>
1 <C -> <C 0

Consider the longitudinal head h = <C^-1 B>.

We must work out how this new head interacts with the tape symbols. To do this, we will still have to break it up into its component heads and simulate it with our rules for normal heads. But things are slightly different, since we can create and destroy pairs of matching heads.

h 0
<C^-1 B> 0
<C^-1 <C 1
1

Therefore, h 0 -> 1.

h 1
<C^-1 B> 1
<C^-1 1 B>
<C^-1 1 <C <C^-1 B>
<C^-1 1 <C h
<C^-1 <C 0 h
0 h

Therefore, h 1 -> 0 h.

Behold these new rules. Unlike in normal forward simulation, when a longitudinal head interacts with tape symbols, the head can change in number - one head can be used up and disappear; also, in some TMs (not this one), we see one head pass through a symbol and become two heads. Of course, one head might also appear to just pass through a symbol and remain the same head. Also, consider the tape symbol in the rule h 1 -> 0 h. It has changed from 1 to 0. Even though there is a head to the right of the 0, we are actually looking at this tape symbol as if right now it is to the right of the head in normal forward simulation, since we have already computed what happens when <C passes through it on the way back to the left.

Let's see how we can use this to analyze the binary counter I mentioned. At step 4, the simulation is $ B> 01 $ ($ is just shorthand for the endless string of zeros at either end of the tape). It looks like when the head reaches the left end of the tape, rule 3 from above always gets applied, so the head will always be B>. So, we might as well assume for the sake of our analysis that this will happen infinitely many times. We replace the simulation with h^inf 01 $.

Infinite head cycles

h^inf means there is a sequence of infinitely many h heads.

When I started working with infinite longitudinal heads, I kept making a certain mistake. Just because h 1 -> 0 h is true doesn't mean that we can do this: h^inf 1 -> 0 h^inf (BAD). Do you see what went wrong? If we write out the longitudinal simulation more explicitly, we have

h^inf 1
...h h h 1
...h h 0 h
...h   1 h

and so on. So we can't just repeatedly apply the rule for h 1. But the following analysis works:

h^inf 1
(h h)^inf 1
(1^-1 h h 1)^inf
(1^-1 h 0 h)^inf
(1^-1 1 h)^inf
h^inf

Therefore h^inf 1 -> h^inf, that is, an infinite sequence of h heads can pass through a 1 symbol and remain as an infinite sequence of h heads. In line 3 of the above analysis, we introduced the use of inverse symbols, which work analogously to inverse heads. Line 2 is in fact equivalent to line 3 (to see this, write out multiple repeats of the cycle and see how the symbols and inverse symbols cancel out). A limitation of this notation is that we no longer keep track of a tape symbol after the infinite head cycle has passed through it (line 6).

We can similarly derive the rule h^inf 0 -> h^inf. Now, we are equipped to run a longitudinal simulation of the binary counter:

h^inf 01 0^inf
h^inf 1 0^inf
h^inf 0^inf

At this point, we reach an infinite loop of h^inf 0^inf -> h^inf 0^inf. For this machine, the head will travel arbitrarily far down the tape to the right and never halt.

Advanced example of infinite head cycles

More complicated solution by dyuan. 1RB1LC_0RC1LF_1LD0RE_0LA0LE_0LA0LB_0LC---.

...

Regarding 1RB---_1LC1RB_0RB0LC, we can also derive rules for multiple heads, such as h^2 0 -> 0 h, h^2 1 -> 1 h.

(work in progress)