Longitudinal Analysis

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.

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

	[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}$