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.

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

$$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\$]$$

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+2) [22] -> [42] B(n)

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

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

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, 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$]

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) [$] -> [44] [42] B(n) [$]

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

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

Now I will state my inductive claim: Given $\dots B(a_{2})\;B(a_{1})\;B(a_{0})\;B(b)\;[\$]$ where $a_{0}\leq a_{1}\leq a_{2}\dots$ and one of the following:

• $a_{0}+1\geq 3b\;{\textrm {and}}\;b\geq 1$ or
• $a_{0}\geq 3\;{\textrm {and}}\;b=0$

You can reach a tape of the form $\dots B(a_{2})\;B(a_{1})\;B(a_{0})\;B(b)\;[\$]$ 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

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.