User:Hipparcos/Longitudinal analysis - Revision history

Hipparcos: revise intro

2026-10-19T04:09:53Z

revise intro

← Older revision		Revision as of 04:09, 19 October 2026
Line 1:		Line 1:
	'''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 ~~and use ``~~inverse heads''.		'''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?! ==		== What is an inverse head?! ==

Hipparcos: revise intro to reduce the priority of "inverse heads"

2026-10-19T04:08:18Z

revise intro to reduce the priority of "inverse heads"

← Older revision		Revision as of 04:08, 19 October 2026
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~~. 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.		'''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 and use ``inverse heads''.

	== What is an inverse head?! ==		== What is an inverse head?! ==

Hipparcos: finish simple example

2026-10-18T23:18:27Z

finish simple example

@@ Line 64: / Line 64: @@
 ==Infinite head cycles==
-When I started working with infinite longitudinal heads, I kept making a certain mistake. Just because <code>h 1 -> 0 h</code> is true doesn't mean that we can do this: <code>h^inf 1 -> 0 h^inf</code> (BAD).  Do you see what went wrong?
+<code>h^inf</code> means there is a sequence of infinitely many <code>h</code> heads.
 ...
-We can also apply these rules we just derived to figure out rules for multiple heads, such as <code>h^2 0 -> 0 h</code>, <code>h^2 1 -> 1 h</code>.
+Regarding <code>1RB---_1LC1RB_0RB0LC</code>, we can also derive rules for multiple heads, such as <code>h^2 0 -> 0 h</code>, <code>h^2 1 -> 1 h</code>.
 (work in progress)

Hipparcos: /* Longitudinal heads */ add clarification

2026-10-16T22:21:13Z

Longitudinal heads: add clarification

← Older revision		Revision as of 22:21, 16 October 2026
Line 59:		Line 59:
	Therefore, <code>h 1 -> 0 h</code>.		Therefore, <code>h 1 -> 0 h</code>.

	We can also ~~apply these rules~~ we just ~~derived to figure out rules for multiple heads~~, ~~such as~~ <code>h~~^2 0~~ -> 0 h</code>, <code>~~h^2~~ 1 -> ~~1 h~~</code>.		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 <code>h 1 -> 0 h</code>. It has changed from <code>1</code> to <code>0</code>. Even though there is a head to the right of the <code>0</code>, 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 <code><C</code> 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 <code>$ B> 01 $</code> (<code>$</code> 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 <code>B></code>. So, we might as well assume for the sake of our analysis that this will happen infinitely many times. We replace the simulation with <code>h^inf 01 $</code>.		Let's see how we can use this to analyze the binary counter I mentioned. At step 4, the simulation is <code>$ B> 01 $</code> (<code>$</code> 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 <code>B></code>. So, we might as well assume for the sake of our analysis that this will happen infinitely many times. We replace the simulation with <code>h^inf 01 $</code>.

	==Infinite head cycles==		==Infinite head cycles==
	When I started working with infinite longitudinal heads, I ~~keep~~ making a certain mistake. Just because <code>h 1 -> 0 h</code> is true doesn't mean that we can do this: <code>h^inf 1 -> 0 h^inf</code> (BAD). Do you see what went wrong?		When I started working with infinite longitudinal heads, I kept making a certain mistake. Just because <code>h 1 -> 0 h</code> is true doesn't mean that we can do this: <code>h^inf 1 -> 0 h^inf</code> (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 <code>h^2 0 -> 0 h</code>, <code>h^2 1 -> 1 h</code>.

	(work in progress)		(work in progress)

Hipparcos: explained longitudinal head; start talking about infinite heads

2026-10-16T22:03:47Z

explained longitudinal head; start talking about infinite heads

@@ Line 5: / Line 5: @@
 A> 1101
 <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>. (Technically, we are also allowed to move the <code><B</code> that we have created, but I choose to only move the <code>A></code> for now.) We hope to see something like this: <syntaxhighlight line="1" lang="text">
+</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>. (Technically, we are also allowed to move the <code><B</code> that we have created, but I choose to only move the <code>A></code> for now.) We hope to see something like this: <syntaxhighlight line="2" lang="text">
 <B <B^-1 A> 1101 (other symbols)
 <B <B^-1 0110 C> (other symbols)
@@ Line 16: / Line 16: @@
 However, if the head comes back as some different state, then our analysis is invalid!
-<syntaxhighlight line="1" lang="text">
+<syntaxhighlight line="2" lang="text">
 <B <B^-1 A> 1101 (other symbols)
 ...a bunch of steps later...
@@ Line 26: / Line 26: @@
 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 analysis by example ==
+== Longitudinal heads ==
-Below, I present examples of longitudinal analysis applied to several different kinds of machines.
+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 <code>1RB---_1LC1RB_0RB0LC</code>. If you look at the simulation of this TM, you'll see that the head going right is always <code>B></code>, and the head going left is always <code><C</code>.

Hipparcos: /* What is an inverse head?! */ finish section

2026-10-15T22:35:14Z

What is an inverse head?!: finish section

← Older revision		Revision as of 22:35, 15 October 2026
Line 5:		Line 5:
	100 A> 1101		100 A> 1101
	100 <B <B^-1 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>. We hope to see something like this: <syntaxhighlight line="1" lang="text">		</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>. (Technically, we are also allowed to move the <code><B</code> that we have created, but I choose to only move the <code>A></code> for now.) We hope to see something like this: <syntaxhighlight line="1" lang="text">
	100 <B <B^-1 A> 1101 (other symbols)		100 <B <B^-1 A> 1101 (other symbols)
	100 <B <B^-1 0110 C> (other symbols)		100 <B <B^-1 0110 C> (other symbols)
Line 24:		Line 24:
	We should have predicted the correct head. Fortunately for us, for some TMs, this is easy to do.		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.		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 analysis by example ==
			Below, I present examples of longitudinal analysis applied to several different kinds of machines.

Hipparcos: /* What is an inverse head?! */ clarify

2026-10-15T22:22:07Z

What is an inverse head?!: clarify

← Older revision		Revision as of 22:22, 15 October 2026
Line 2:		Line 2:

	== What is an inverse head?! ==		== 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" lang="text">		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 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:<syntaxhighlight line="1" lang="text">
	100 A> 1101		100 A> 1101
	100 <B <B^-1 A> 1101		100 <B <B^-1 A> 1101

Hipparcos: more on inverse heads

2026-10-15T22:21:29Z

Hipparcos: more on inverse heads

2026-10-15T22:14:35Z

Hipparcos: write about inverse heads

2026-10-15T22:07:53Z

write about inverse heads

← Older revision		Revision as of 22:07, 15 October 2026
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. ~~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.		'''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>.

← Older revision		Revision as of 22:21, 15 October 2026
Line 23:		Line 23:
	</syntaxhighlight>		</syntaxhighlight>
	We should have predicted the correct head. Fortunately for us, for some TMs, this is easy to do.		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.

@@ Line 2: / Line 2: @@
 == 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">
+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" lang="text">
 A> 1101
 <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>.
+</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>. We hope to see something like this: <syntaxhighlight line="1" lang="text">