Longitudinal Analysis

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

A Block Analysis of 1RB4LA1LB2LA0RB_2LB3RB4LA---1RA provides the following rules:

	[2]	[22]	[24]	[42]	[44]	[4$]	[2$]	[22$]	[24$]	[42$]	[44$]
[B>]	[<A] [4>]	[<A] [42]	[<A] [44]	[33] [B>]	[10] [B>]	[<A] [42] [4$]	[<A] [4$]	[<A] [42$]	[<A] [44$]	Halt	[<A] [24] [2$]
[4>]	[42]	[42] [2]	[42] [4>]	[44] [2]	[44] [4>]	[44$]	[42$]	[42] [2$]	[42] [4$]	[44] [2$]	[44] [4$]

	[33]	[10]	[11]	[$1]
[<A]	[<A] [22]	[11] [B>]	[<A] [44]	[$1] [B>] [4>]

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:

$$[{\textrm {<A}}^{-1}]\;[33]\;\rightarrow \;[{\textrm {<A}}^{-1}]\;[33]\;[{\textrm {<A}}]\;[{\textrm {<A}}^{-1}]\;\rightarrow \;[{\textrm {<A}}^{-1}]\;[{\textrm {<A}}]\;[22]\;[{\textrm {<A}}^{-1}]\;\rightarrow \;[22]\;[{\textrm {<A}}^{-1}]$$

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:

$$[{\textrm {<A}}^{-1}\;{\textrm {B>}}][24]\rightarrow [{\textrm {<A}}^{-1}][{\textrm {B>}}][24]\rightarrow [{\textrm {<A}}^{-1}][{\textrm {<A}}][44]\rightarrow [44]$$

$$[{\textrm {<A}}^{-1}\;{\textrm {B>}}][42]\rightarrow [{\textrm {<A}}^{-1}][{\textrm {B>}}][42]\rightarrow [{\textrm {<A}}^{-1}][33][{\textrm {B>}}]\rightarrow [{\textrm {<A}}^{-1}][33][{\textrm {<A}}][{\textrm {<A}}^{-1}\;{\textrm {B>}}]\rightarrow [{\textrm {<A}}^{-1}][{\textrm {<A}}][22][{\textrm {<A}}^{-1}\;{\textrm {B>}}]\rightarrow [22][{\textrm {<A}}^{-1}\;{\textrm {B>}}]$$

$[{\textrm {<A}}^{-1}\;{\textrm {B>}}][44]\rightarrow [{\textrm {<A}}^{-1}][{\textrm {B>}}][44]\rightarrow [{\textrm {<A}}^{-1}][10][{\textrm {B>}}]\rightarrow [{\textrm {<A}}^{-1}][10][{\textrm {<A}}][{\textrm {<A}}^{-1}\;{\textrm {B>}}]\rightarrow [{\textrm {<A}}^{-1}][11][{\textrm {B>}}][{\textrm {<A}}^{-1}\;{\textrm {B>}}]\rightarrow [{\textrm {<A}}^{-1}][11][{\textrm {<A}}][{\textrm {<A}}^{-1}\;{\textrm {B>}}][{\textrm {<A}}^{-1}\;{\textrm {B>}}]\rightarrow [{\textrm {<A}}^{-1}][{\textrm {<A}}][44][{\textrm {<A}}^{-1}\;{\textrm {B>}}]^{2}\rightarrow [44][{\textrm {<A}}^{-1}\;{\textrm {B>}}]^{2}$We can modify the first table from our block analysis to get this new table:

	[2]	[22]	[24]	[42]	[44]	[4$]	[2$]	[22$]	[24$]	[42$]	[44$]
[<A^-1 B>]	[4>]	[42]	[44]	[22] [<A^-1 B>]	[44] [<A^-1 B>]^2	[42] [4$]	[4$]	[42$]	[44$]	Halt	[24] [2$]
[4>]	[42]	[42] [2]	[42] [4>]	[44] [2]	[44] [4>]	[44$]	[42$]	[42] [2$]	[42] [4$]	[44] [2$]	[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:

$$[\$1\;{\textrm {<A}}]\rightarrow [\$1][{\textrm {<A}}]\rightarrow [\$1][{\textrm {B>}}][4>]\rightarrow [\$1\;{\textrm {<A}}][{\textrm {<A}}^{-1}\;{\textrm {B>}}][4>]$$

At the end, you get the full transition table:

From	To
[$1 <A]	[$1 <A] [<A^-1 B>] [4>]

	[2]	[22]	[24]	[42]	[44]	[4$]	[2$]	[22$]	[24$]	[42$]	[44$]
[<A^-1 B>]	[4>]	[42]	[44]	[22] [<A^-1 B>]	[44] [<A^-1 B>]^2	[42] [4$]	[4$]	[42$]	[44$]	Halt	[24] [2$]
[4>]	[42]	[42] [2]	[42] [4>]	[44] [2]	[44] [4>]	[44$]	[42$]	[42] [2$]	[42] [4$]	[44] [2$]	[44] [4$]

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

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

Warnings

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