User:Hipparcos/Longitudinal analysis: Difference between revisions
start page |
write about inverse heads |
||
| Line 1: | Line 1: | ||
'''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. | '''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 <code>100 A> 1101</code>. 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:<syntaxhighlight line="1"> | |||
100 A> 1101 | |||
100 <B <B^-1 A> 1101 | |||
</syntaxhighlight>This inverse head <code><B^-1</code> is a prediction. Specifically, we are predicting that after the head <code>A></code> continues to travel to the right, ''if and when'' it returns back to this spot, it will return as a <code><B</code>. At that point, it can cancel out with the inverse head <code><B^-1</code>. | |||
Revision as of 22:07, 15 October 2026
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> 1101This 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.