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 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. 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.