Longitudinal Analysis - Revision history

MrSolis: who wrote this?

2025-10-07T23:31:54Z

who wrote this?

← Older revision		Revision as of 23:31, 7 October 2025
Line 60:		Line 60:
	Starting from: [$1] [B>] [24$]		Starting from: [$1] [B>] [24$]

	Note that the ''only'' possible interaction with any of the left blocks ([33], [10], [11], and [$1]) can be with [<A]. So we can predict that ahead of time and "borrow" an [<A], along with an [<A^-1] indicating that an [<A] has been borrowed. So a possible simulation in Longitudinal Analysis could look like this:<math display="block">[\textrm{<A}^{-1}] \; [33] \; \rightarrow \; [\textrm{<A}^{-1}] \; [33] \; [\textrm{<A}] \;		Note that the ''only'' possible interaction with any of the left blocks ([33], [10], [11], and [$1]) can be with [<A]. So we can predict that ahead of time and "borrow" an [<A], along with an [<A^-1] indicating that an [<A] has been borrowed. So a possible simulation in Longitudinal Analysis could look like this:<math display="block">[\textrm{<}\textrm{A}^{-1}] \; [33] \; \rightarrow \; [\textrm{<}\textrm{A}^{-1}] \; [33] \; [\textrm{<}\textrm{A}] \;
	[\textrm{<A}^{-1}] \; \rightarrow \; [\textrm{<A}^{-1}] \; [\textrm{<A}] \; [22] \; [\textrm{<A}^{-1}]		[\textrm{<}\textrm{A}^{-1}] \; \rightarrow \; [\textrm{<}\textrm{A}^{-1}] \; [\textrm{<}\textrm{A}] \; [22] \; [\textrm{<}\textrm{A}^{-1}]
	\; \rightarrow \; [22] \; [\textrm{<A}^{-1}]</math>		\; \rightarrow \; [22] \; [\textrm{<}\textrm{A}^{-1}]</math>

	What makes this so useful is that we can pair [<A^-1] with [B>] to create a new block: [<A^-1 B>]. Let's see what we can do with this new type of block:<math display="block">[\textrm{<A}^{-1} \; \textrm{B>}] [24] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][24] \rightarrow		What makes this so useful is that we can pair [<A^-1] with [B>] to create a new block: [<A^-1 B>]. Let's see what we can do with this new type of block:<math display="block">[\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}] [24] \rightarrow [\textrm{<}\textrm{A}^{-1}][\textrm{B}\textrm{>}][24] \rightarrow
	[\textrm{<A}^{-1}][\textrm{<A}][44] \rightarrow [44]</math><math display="block">[\textrm{<A}^{-1} \; \textrm{B>}][42] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][42] \rightarrow		[\textrm{<}\textrm{A}^{-1}][\textrm{<}\textrm{A}][44] \rightarrow [44]</math><math display="block">[\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}][42] \rightarrow [\textrm{<}\textrm{A}^{-1}][\textrm{B}\textrm{>}][42] \rightarrow
	[\textrm{<A}^{-1}][33][\textrm{B>}] \rightarrow		[\textrm{<}\textrm{A}^{-1}][33][\textrm{B}\textrm{>}] \rightarrow
	[\textrm{<A}^{-1}][33][\textrm{<A}][\textrm{<A}^{-1} \; \textrm{B>}] \rightarrow		[\textrm{<}\textrm{A}^{-1}][33][\textrm{<}\textrm{A}][\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}] \rightarrow
	[\textrm{<A}^{-1}][\textrm{<A}][22][\textrm{<A}^{-1} \; \textrm{B>}] \rightarrow		[\textrm{<}\textrm{A}^{-1}][\textrm{<}\textrm{A}][22][\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}] \rightarrow
	[22][\textrm{<A}^{-1} \; \textrm{B>}]</math><math>[\textrm{<A}^{-1} \; \textrm{B>}][44] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][44] \rightarrow		[22][\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}]</math><math>[\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}][44] \rightarrow [\textrm{<}\textrm{A}^{-1}][\textrm{B}\textrm{>}][44] \rightarrow
	[\textrm{<A}^{-1}][10][\textrm{B>}] \rightarrow		[\textrm{<}\textrm{A}^{-1}][10][\textrm{B}\textrm{>}] \rightarrow
	[\textrm{<A}^{-1}][10][\textrm{<A}][\textrm{<A}^{-1}\;\textrm{B>}] \rightarrow		[\textrm{<}\textrm{A}^{-1}][10][\textrm{<}\textrm{A}][\textrm{<}\textrm{A}^{-1}\;\textrm{B}\textrm{>}] \rightarrow
	[\textrm{<A}^{-1}][11][\textrm{B>}][\textrm{<A}^{-1}\;\textrm{B>}] \rightarrow		[\textrm{<}\textrm{A}^{-1}][11][\textrm{B}\textrm{>}][\textrm{<}\textrm{A}^{-1}\;\textrm{B}\textrm{>}] \rightarrow
	[\textrm{<A}^{-1}][11][\textrm{<A}][\textrm{<A}^{-1}\;\textrm{B>}][\textrm{<A}^{-1}\;\textrm{B>}]		[\textrm{<}\textrm{A}^{-1}][11][\textrm{<}\textrm{A}][\textrm{<}\textrm{A}^{-1}\;\textrm{B}\textrm{>}][\textrm{<}\textrm{A}^{-1}\;\textrm{B}\textrm{>}]
	\rightarrow [\textrm{<A}^{-1}][\textrm{<A}][44][\textrm{<A}^{-1}\;\textrm{B>}]^2 \rightarrow		\rightarrow [\textrm{<}\textrm{A}^{-1}][\textrm{<}\textrm{A}][44][\textrm{<}\textrm{A}^{-1}\;\textrm{B}\textrm{>}]^2 \rightarrow
	[44][\textrm{<A}^{-1}\;\textrm{B>}]^2		[44][\textrm{<}\textrm{A}^{-1}\;\textrm{B}\textrm{>}]^2
	</math>We can modify the first table from our block analysis to get this new table:		</math>We can modify the first table from our block analysis to get this new table:
	{\| class="wikitable"		{\| class="wikitable"
Line 117:		Line 117:
	\|[44] [4$]		\|[44] [4$]
	\|}Our current starting position is [$1] [B>] [24$], which can also be [$1] [<A] [<A^-1 B>] [24$]. One last change, we can almost completely get rid of [<A]. If we combine [$1] and [<A], we will get [$1 <A], which can be simulated by itself:		\|}Our current starting position is [$1] [B>] [24$], which can also be [$1] [<A] [<A^-1 B>] [24$]. One last change, we can almost completely get rid of [<A]. If we combine [$1] and [<A], we will get [$1 <A], which can be simulated by itself:
	<math display="block">[\$1 \; \textrm{<A}] \rightarrow [\$1][\textrm{<A}] \rightarrow [\$1][\textrm{B>}][4>] \rightarrow		<math display="block">[\$1 \; \textrm{<}\textrm{A}] \rightarrow [\$1][\textrm{<}\textrm{A}] \rightarrow [\$1][\textrm{B}\textrm{>}][4>] \rightarrow
	[\$1 \; \textrm{<A}][\textrm{<A}^{-1} \; \textrm{B>}][4>]</math>At the end, you get the full transition table:		[\$1 \; \textrm{<}\textrm{A}][\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}][4>]</math>At the end, you get the full transition table:
	{\| class="wikitable"		{\| class="wikitable"
	\|+		\|+
Line 176:		Line 176:
	The standard way to proceed is to analyze each individual block to infinity one at a time, then progressing cell by cell rather than time, hence the name "Longitudinal." We will see how this type of analysis can produce results that may not be noticeable in a direct forward analysis. In our previous example, we start with the edge block [$1 <A] and apply the rule infinite times to get [$1 <A] ([<A^-1 B>] [4>])^inf. Our starting position would now be [$1 <A] ([<A^-1 B>] [4>])^inf [<A^-1 B>] [24$]. Now the [$1 <A] is irrelevant, so we can actually get away with just writing ([<A^-1 B>] [4>])^inf [<A^-1 B>] [24$] -> ([<A^-1 B>] [4>])^inf [44$]. For this TM, let's define B(n) = [<A^-1 B>]^n [4>], so our tape becomes (B(1))^inf [44$]. Let's first take out a B(1) and interact it with [44$] to get		The standard way to proceed is to analyze each individual block to infinity one at a time, then progressing cell by cell rather than time, hence the name "Longitudinal." We will see how this type of analysis can produce results that may not be noticeable in a direct forward analysis. In our previous example, we start with the edge block [$1 <A] and apply the rule infinite times to get [$1 <A] ([<A^-1 B>] [4>])^inf. Our starting position would now be [$1 <A] ([<A^-1 B>] [4>])^inf [<A^-1 B>] [24$]. Now the [$1 <A] is irrelevant, so we can actually get away with just writing ([<A^-1 B>] [4>])^inf [<A^-1 B>] [24$] -> ([<A^-1 B>] [4>])^inf [44$]. For this TM, let's define B(n) = [<A^-1 B>]^n [4>], so our tape becomes (B(1))^inf [44$]. Let's first take out a B(1) and interact it with [44$] to get

	<math display="block">B(1) \; [44\$] \rightarrow [\textrm{<A}^{-1} \; \textrm{B>}] [4>] [44\$]		<math display="block">B(1) \; [44\$] \rightarrow [\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}] [4>] [44\$]
	\rightarrow [\textrm{<A}^{-1} \; \textrm{B>}] [44] [4\$] \rightarrow		\rightarrow [\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}] [44] [4\$] \rightarrow
	[44] [\textrm{<A}^{-1} \; \textrm{B>}]^2 [4\$] \rightarrow		[44] [\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}]^2 [4\$] \rightarrow
	[44] [\textrm{<A}^{-1} \; \textrm{B>}] [42] [4\$] \rightarrow		[44] [\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}] [42] [4\$] \rightarrow
	[44] [22] [\textrm{<A}^{-1} \; \textrm{B>}] [4\$] \rightarrow		[44] [22] [\textrm{<}\textrm{A}^{-1} \; \textrm{B}\textrm{>}] [4\$] \rightarrow
	[44] [22] [42] [4\$]</math>		[44] [22] [42] [4\$]</math>

Line 221:		Line 221:
	Now I will state my inductive claim: Given <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> where <math>a_0\leq a_1 \leq a_2\dots </math> and one of the following:		Now I will state my inductive claim: Given <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> where <math>a_0\leq a_1 \leq a_2\dots </math> and one of the following:

	* <math>a_0+1 \geq 3b \~~;\textrm~~{and}\; b \geq 1</math> or		* <math>a_0+1 \geq 3b\text{ and }b \geq 1</math> or
	* <math>a_0 \geq 3 \~~; \textrm~~{and} \; b=0</math>		* <math>a_0 \geq 3\text{ and }b=0</math>

	You can reach a tape of the form <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> again with the same conditions.		You can reach a tape of the form <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> again with the same conditions.

Int-y1: bold name

2025-08-25T08:45:03Z

bold name

← Older revision		Revision as of 08:45, 25 August 2025
Line 1:		Line 1:
	Longitudinal Analysis is a type of analysis on a TM, where, instead of analyzing the TM based on its direct forward behavior, takes advantage of a certain property of the TM which allows you to predict certain interactions ahead of time and simulate steps out of order. The best way to explain this is through an example.		'''Longitudinal Analysis''' is a type of analysis on a TM, where, instead of analyzing the TM based on its direct forward behavior, takes advantage of a certain property of the TM which allows you to predict certain interactions ahead of time and simulate steps out of order. The best way to explain this is through an example.

	== Example TM: 1RB4LA1LB2LA0RB_2LB3RB4LA---1RA ==		== Example TM: 1RB4LA1LB2LA0RB_2LB3RB4LA---1RA ==

Dyuan01: /* Standard Longitudinal Analysis (and Example Proof) */

2024-11-13T19:44:00Z

Standard Longitudinal Analysis (and Example Proof)

← Older revision		Revision as of 19:44, 13 November 2024
Line 207:		Line 207:
	(B(4))^inf B(3) B(0) B(0) [42] [4$]		(B(4))^inf B(3) B(0) B(0) [42] [4$]

	But now we run into a rule that's not handled by the rules we derived, so we have to leave our universe of rules and start thinking about the tape individually. This is the only time in the analysis where this happens. Note that B(0) is just a 4 symbol, so two 4 symbols become a [44] block. So we have		But now we run into a rule that's not handled by the rules we derived, so we have to leave our universe of rules and start thinking about the tape individually. This is the only time in the analysis where this happens. Note that B(0) is just a 4 symbol, and two 4 symbols become a [44] block. So we have

	(B(4))^inf B(3) [44] [42] [4$] -> (B(8))^inf B(6) [42] [4$] -> (B(16))^inf B(11) [4$]		(B(4))^inf B(3) [44] [42] [4$] -> (B(8))^inf B(6) [42] [4$] -> (B(16))^inf B(11) [4$]

Dyuan01: /* Standard Longitudinal Analysis (and Example Proof) */ added something that hopefully makes the proof I left for the reader easier

2024-11-13T19:38:40Z

Standard Longitudinal Analysis (and Example Proof): added something that hopefully makes the proof I left for the reader easier

← Older revision		Revision as of 19:38, 13 November 2024
Line 213:		Line 213:
	Note that [4$] is equivalent to [4>] [$], so we will do that to get (B(16))^inf B(11) B(0) [$], and we also get these rules:		Note that [4$] is equivalent to [4>] [$], so we will do that to get (B(16))^inf B(11) B(0) [$], and we also get these rules:

	B(n+3) B(0) [$] -> [44] B(2n+1) [$]		B(n+3) B(0) [$] -> [44] B(2n+1) [$] -> [44] [42] B(n) [$]

	B(2n+1) [$] -> [42] B(n) [$]		B(2n+1) [$] -> [42] B(n) [$]

Dyuan01: /* Standard Longitudinal Analysis (and Example Proof) */ finished the section

2024-11-13T19:35:27Z

Standard Longitudinal Analysis (and Example Proof): finished the section

← Older revision		Revision as of 19:35, 13 November 2024
Line 210:		Line 210:

	(B(4))^inf B(3) [44] [42] [4$] -> (B(8))^inf B(6) [42] [4$] -> (B(16))^inf B(11) [4$]		(B(4))^inf B(3) [44] [42] [4$] -> (B(8))^inf B(6) [42] [4$] -> (B(16))^inf B(11) [4$]

			Note that [4$] is equivalent to [4>] [$], so we will do that to get (B(16))^inf B(11) B(0) [$], and we also get these rules:

			B(n+3) B(0) [$] -> [44] B(2n+1) [$]

			B(2n+1) [$] -> [42] B(n) [$]

			B(2n+2) [$] -> [22] B(n+1) [$]

			Now I will state my inductive claim: Given <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> where <math>a_0\leq a_1 \leq a_2\dots </math> and one of the following:

			* <math>a_0+1 \geq 3b \;\textrm{and}\; b \geq 1</math> or
			* <math>a_0 \geq 3 \; \textrm{and} \; b=0</math>

			You can reach a tape of the form <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> again with the same conditions.

			I will not prove this on this page, as it is a bit tedious, but hopefully the idea is clear enough that you'll just accept it for the sake of understanding the purpose of Longitudinal Analysis. Afterwards, since we've reached a position that satisfies the inductive condition, we know it will stay like that forever without halting.

	== Warnings ==		== Warnings ==

Sligocki: rm stub

2024-11-13T17:37:19Z

rm stub

← Older revision		Revision as of 17:37, 13 November 2024
Line 218:		Line 218:
	Conversely, if you find a halting interaction during analysis, you need an extra condition that simply shows that the halting transition will eventually happen: any block to the right of the halting location (or left if your rules are mirrored) must eventually die out. If it does not, then that means in the original TM, when we assumed that the head would eventually come back as [<A], it actually never comes back, becoming a translated cycler or for another reason.		Conversely, if you find a halting interaction during analysis, you need an extra condition that simply shows that the halting transition will eventually happen: any block to the right of the halting location (or left if your rules are mirrored) must eventually die out. If it does not, then that means in the original TM, when we assumed that the head would eventually come back as [<A], it actually never comes back, becoming a translated cycler or for another reason.
	[[Category:Analysis Techniques]]		[[Category:Analysis Techniques]]
	~~[[Category:Stub]]~~

Dyuan01: /* Standard Longitudinal Analysis (and Example Proof) */ Added more stuff (still not done yet)

2024-11-13T16:36:36Z

Standard Longitudinal Analysis (and Example Proof): Added more stuff (still not done yet)

← Older revision		Revision as of 16:36, 13 November 2024
Line 183:		Line 183:
	[44] [22] [42] [4\$]</math>		[44] [22] [42] [4\$]</math>

	So now we have (B(1))^inf [42] [22] [42] [4$]. Now, we can derive these rules:		So now we have (B(1))^inf [42] [22] [42] [4$]. Now, we can derive these rules (left as an exercise for the reader):

	B(2n+1) [22] -> [22] B(n)		B(2n+1) [22] -> [22] B(n)
Line 193:		Line 193:
	B(n) [44] -> [44] B(2n)		B(n) [44] -> [44] B(2n)

	I ~~will now show~~ that if we ~~start with~~ B(i) B(j) ([22] or [42] or [44]) and i >= j, then we will end with		I'll also claim that if we have B(i_0) B(j_0) ([22] or [42] or [44]) and i_0 >= j_0 >= 1, then we will end with ([22] or [42] or [44]) B(i_1) B(j_1) and i_1 >= j_1. This applies to any number of variables (also left as an exercise for the reader)

			We haven't yet developed a set of closed rules, but we're getting there. We still need one more condition that is not yet met in our current tape, so let's simulate it until we get that condition:

			Let's take another step in our longitudinal analysis: (B(1))^inf [42] -> (B(1))^inf B(1) [42] -> (B(1))^inf [44] B(1) -> [44] (B(2))^inf B(1)

			Our [44] is now irrelevant, so we can remove it:

			(B(2))^inf B(1) [22] [42] [4$]

			We repeat this process to get

			(B(4))^inf B(3) B(0) B(0) [42] [4$]

			But now we run into a rule that's not handled by the rules we derived, so we have to leave our universe of rules and start thinking about the tape individually. This is the only time in the analysis where this happens. Note that B(0) is just a 4 symbol, so two 4 symbols become a [44] block. So we have

			(B(4))^inf B(3) [44] [42] [4$] -> (B(8))^inf B(6) [42] [4$] -> (B(16))^inf B(11) [4$]

	== Warnings ==		== Warnings ==
Line 202:		Line 218:
	Conversely, if you find a halting interaction during analysis, you need an extra condition that simply shows that the halting transition will eventually happen: any block to the right of the halting location (or left if your rules are mirrored) must eventually die out. If it does not, then that means in the original TM, when we assumed that the head would eventually come back as [<A], it actually never comes back, becoming a translated cycler or for another reason.		Conversely, if you find a halting interaction during analysis, you need an extra condition that simply shows that the halting transition will eventually happen: any block to the right of the halting location (or left if your rules are mirrored) must eventually die out. If it does not, then that means in the original TM, when we assumed that the head would eventually come back as [<A], it actually never comes back, becoming a translated cycler or for another reason.
	[[Category:Analysis Techniques]]		[[Category:Analysis Techniques]]
			[[Category:Stub]]

Dyuan01: Edit, but still a stub

2024-11-13T15:52:07Z

Edit, but still a stub

← Older revision		Revision as of 15:52, 13 November 2024
Line 170:		Line 170:

	Note that we completely omitted [<A] from our set of blocks, since we have fully predicted when [<A] arrives.		Note that we completely omitted [<A] from our set of blocks, since we have fully predicted when [<A] arrives.

			There are multiple ways to proceed with analysis, but I will show the standard way:

			== Standard Longitudinal Analysis (and Example Proof) ==
			The standard way to proceed is to analyze each individual block to infinity one at a time, then progressing cell by cell rather than time, hence the name "Longitudinal." We will see how this type of analysis can produce results that may not be noticeable in a direct forward analysis. In our previous example, we start with the edge block [$1 <A] and apply the rule infinite times to get [$1 <A] ([<A^-1 B>] [4>])^inf. Our starting position would now be [$1 <A] ([<A^-1 B>] [4>])^inf [<A^-1 B>] [24$]. Now the [$1 <A] is irrelevant, so we can actually get away with just writing ([<A^-1 B>] [4>])^inf [<A^-1 B>] [24$] -> ([<A^-1 B>] [4>])^inf [44$]. For this TM, let's define B(n) = [<A^-1 B>]^n [4>], so our tape becomes (B(1))^inf [44$]. Let's first take out a B(1) and interact it with [44$] to get

			<math display="block">B(1) \; [44\$] \rightarrow [\textrm{<A}^{-1} \; \textrm{B>}] [4>] [44\$]
			\rightarrow [\textrm{<A}^{-1} \; \textrm{B>}] [44] [4\$] \rightarrow
			[44] [\textrm{<A}^{-1} \; \textrm{B>}]^2 [4\$] \rightarrow
			[44] [\textrm{<A}^{-1} \; \textrm{B>}] [42] [4\$] \rightarrow
			[44] [22] [\textrm{<A}^{-1} \; \textrm{B>}] [4\$] \rightarrow
			[44] [22] [42] [4\$]</math>

			So now we have (B(1))^inf [42] [22] [42] [4$]. Now, we can derive these rules:

			B(2n+1) [22] -> [22] B(n)

			B(2n+2) [22] -> [42] B(n)

			B(n+1) [42] -> [44] B(2n+1)

			B(n) [44] -> [44] B(2n)

			I will now show that if we start with B(i) B(j) ([22] or [42] or [44]) and i >= j, then we will end with

	== Warnings ==		== Warnings ==

Dyuan01: Added a point in Warnings and fixed some minor errors.

2024-11-13T15:24:32Z

Added a point in Warnings and fixed some minor errors.

← Older revision		Revision as of 15:24, 13 November 2024
Line 1:		Line 1:
	~~Note: this is currently a stub~~

	Longitudinal Analysis is a type of analysis on a TM, where, instead of analyzing the TM based on its direct forward behavior, takes advantage of a certain property of the TM which allows you to predict certain interactions ahead of time and simulate steps out of order. The best way to explain this is through an example.		Longitudinal Analysis is a type of analysis on a TM, where, instead of analyzing the TM based on its direct forward behavior, takes advantage of a certain property of the TM which allows you to predict certain interactions ahead of time and simulate steps out of order. The best way to explain this is through an example.

Line 171:		Line 169:
	Start: [$1 <A] [<A^-1 B>] [24$]		Start: [$1 <A] [<A^-1 B>] [24$]

	Note that we completely ~~ommitted~~ [<A] from our set of blocks, since we have fully predicted when [<A] arrives.		Note that we completely omitted [<A] from our set of blocks, since we have fully predicted when [<A] arrives.

	== Warnings ==		== Warnings ==
	Because we are now able to simulate steps in different orders, there are different rules to when a TM halts or not. Just because we can make infinite steps without halting doesn't necessarily mean the TM doesn't halt. in our previous example, we can just simply apply rule [$1 <A] -> [$1 <A] [<A^-1 B>] [4>] infinite times to get [$1 <A] ([<A^-1 B>] [4>])^inf [<A^-1 B>] [24$], but we didn't really simulate the important part of the TM. In particular, if we already have two blocks that halt, [<A^-1 B>][42$], we could avoid it indefinitely by constantly making other transitions. However, if we maintain the rule that every possible interaction between blocks will eventually be made, then showing that such a process doesn't lead to halting ''will'' show that the original TM never halts.		The standard way to proceed is to analyze each individual block to infinity one at a time, then progressing cell by cell rather than time, hence the name "Longitudinal." However, the flexibility allows for analysis in any order, with a catch:

			Because we are now able to simulate steps in different orders, there are different rules as to when a TM halts or not. Just because we can make infinite steps without halting doesn't necessarily mean the TM doesn't halt. in our previous example, we can just simply apply rule [$1 <A] -> [$1 <A] [<A^-1 B>] [4>] infinite times to get [$1 <A] ([<A^-1 B>] [4>])^inf [<A^-1 B>] [24$], but we didn't really simulate the important part of the TM. In particular, if we already have two blocks that halt, [<A^-1 B>][42$], we could avoid it indefinitely by constantly making other transitions. However, if we maintain the rule that every possible interaction between blocks will eventually be made, then showing that such a process doesn't lead to halting ''will'' show that the original TM never halts.

	Conversely, if you find ~~that~~ a halting interaction during analysis, you need an extra condition that simply shows that the halting transition will eventually happen: any block to the right of the halting location (or left if your rules are mirrored), must eventually die out. If it does not, then that means in the original TM, when we assumed that the head ~~will~~ eventually come back as [<A], actually never comes back, ~~either~~ becoming a translated cycler, or for ~~some other~~ reason.		Conversely, if you find a halting interaction during analysis, you need an extra condition that simply shows that the halting transition will eventually happen: any block to the right of the halting location (or left if your rules are mirrored) must eventually die out. If it does not, then that means in the original TM, when we assumed that the head would eventually come back as [<A], it actually never comes back, becoming a translated cycler or for another reason.
	[[Category:Analysis Techniques]]		[[Category:Analysis Techniques]]

Dyuan01: fixed some grammar errors

2024-11-10T17:03:25Z

fixed some grammar errors

← Older revision		Revision as of 17:03, 10 November 2024
Line 176:		Line 176:
	Because we are now able to simulate steps in different orders, there are different rules to when a TM halts or not. Just because we can make infinite steps without halting doesn't necessarily mean the TM doesn't halt. in our previous example, we can just simply apply rule [$1 <A] -> [$1 <A] [<A^-1 B>] [4>] infinite times to get [$1 <A] ([<A^-1 B>] [4>])^inf [<A^-1 B>] [24$], but we didn't really simulate the important part of the TM. In particular, if we already have two blocks that halt, [<A^-1 B>][42$], we could avoid it indefinitely by constantly making other transitions. However, if we maintain the rule that every possible interaction between blocks will eventually be made, then showing that such a process doesn't lead to halting ''will'' show that the original TM never halts.		Because we are now able to simulate steps in different orders, there are different rules to when a TM halts or not. Just because we can make infinite steps without halting doesn't necessarily mean the TM doesn't halt. in our previous example, we can just simply apply rule [$1 <A] -> [$1 <A] [<A^-1 B>] [4>] infinite times to get [$1 <A] ([<A^-1 B>] [4>])^inf [<A^-1 B>] [24$], but we didn't really simulate the important part of the TM. In particular, if we already have two blocks that halt, [<A^-1 B>][42$], we could avoid it indefinitely by constantly making other transitions. However, if we maintain the rule that every possible interaction between blocks will eventually be made, then showing that such a process doesn't lead to halting ''will'' show that the original TM never halts.

	Conversely, if you find that a halting interaction during analysis, you need an extra condition that simply shows that the halting transition will eventually happen: any block to the right of the ~~Halting~~ location (or left if your rules are mirrored), must eventually die out. If it does not, then that means in the original TM, when we assumed that the head will eventually come back as [<A], it actually never comes back, either becoming a translated cycler, or for some other reason.		Conversely, if you find that a halting interaction during analysis, you need an extra condition that simply shows that the halting transition will eventually happen: any block to the right of the halting location (or left if your rules are mirrored), must eventually die out. If it does not, then that means in the original TM, when we assumed that the head will eventually come back as [<A], actually never comes back, either becoming a translated cycler, or for some other reason.
	[[Category:Analysis Techniques]]		[[Category:Analysis Techniques]]