User:Hipparcos/Longitudinal analysis

Longitudinal analysis is a way of analyzing Turing machines involving the use of inverse heads. Unlike in the normal forward simulation of a Turing machine, in longitudinal analysis, there can be multiple heads present at once, and the effect of the head on the tape is computed not necessarily in chronological order, but rather on sections of the tape that we are interested in. 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 powerful notation for 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.

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

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?

...

We can also apply these rules we just derived to figure out rules for multiple heads, such as h^2 0 -> 0 h, h^2 1 -> 1 h.

(work in progress)