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. Occasionally, 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 very useful 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.