Block Analysis

Block Analysis is when instead of looking at the head and symbols as individual entities, we group multiple of them into a "block" of symbols (Examples: [10], [102], [10011]). Blocks can be infinite, containing the infinite string of 0s on either side of the tape, generally represented by a dollar sign (Examples: [$10], [101$]). They can also contain the head, assuming Directed Head Notation. Generally the head is always on the outside of the block, pointing outwards (Examples: [1B>], [<C], [102A>], [<D11]).

Example: 1RB---1LC_2RC0LA2LB_1LB0LB0RB

In 66 steps from the starting position, the tape becomes $0^{\infty }\;22212\;{\textrm {<B}}\;201021\;0^{\infty }$, which can be grouped as follows: $[\$2]\;[22]\;[12]\;[{\textrm {<B}}]\;[201021\$]$. The grouping is arbitrary, but it typically has a purpose.

Suppose we want to simulate the TM while the tape is grouped together, we ungroup the head and the block it is pointing to, in this case it's the [12] and the [<B]. And simulate it until the head points outwards:

$$12\;{\textrm {<B}}\;\rightarrow 1\;{\textrm {<B}}\;2\;\rightarrow \;{\textrm {<A}}\;02$$

Finally, we regroup the resulting tape segment however we like. In this case: I want to group everything into one block: [<A02], but any grouping is allowed. So the current tape is now $[\$2]\;[22]\;[{\textrm {<A02}}]\;[201021\$]$. What we've effectively done is created a rule: whenever we see [12] [<B] in that order, replace it with [<A02]. We can do this again with [22] [<A02]: first ungroup, then simulate, then regroup:

$$[22]\;[{\textrm {<A}}02]\;\rightarrow \;22\;{\textrm {<A}}\;02\;\rightarrow \;2\;{\textrm {<C}}\;102\;\rightarrow \;0\;{\textrm {B>}}\;102\;\rightarrow \;0\;{\textrm {<A}}\;002\;\rightarrow \;1\;{\textrm {B>}}\;002\;\rightarrow \;12\;{\textrm {C>}}\;02\;\rightarrow \;12\;{\textrm {<B}}\;12\;\rightarrow \;1\;{\textrm {<B}}\;212\rightarrow \;{\textrm {<A}}\;0212\;\rightarrow \;[{\textrm {<A}}02]\;[12]$$

Note that I regrouped it in such a way that we get [<A02] again. This is intentional, as we want to minimize the block types for our analysis to be effective. In fact, if we restrict blocks to the left of the head to only be [$2], [12], and [22], the blocks to the right of the head to be [12], [22], [0102], and [201021$], and the blocks containing the head to be [<B], [<A02], and [0B>], then we can create a closed set of blocks that can always be regrouped to a different set of these blocks: we can show this using two tables, the first being every block with a left-pointing head interacting with every left block, and every block with a right-pointing head interacting with every right block:

	[$2]	[12]	[22]
[<B]	[$2] [0B>]	[<A02]	[<B] [22]
[<A02]	[$2] [22] [12] [0B>]	[<B] [0102]	[<A02] [12]

	[12]	[22]	[0102]	[201021$]
[0B>]	[12] [0B>]	[22] [0B>]	[22] [12] [0B>]	[<B] [22] [201021$]

It's important to note the tape after can be expressed using the blocks in this closed set after a number of steps.

After 66 steps, the tape becomes $[\$2]\;[22]\;[12]\;[{\textrm {<B}}]\;[201021\$]$, and from that point on, we will always be able to return to another tape using only the blocks we allow without ever halting. Therefore 1RB---1LC_2RC0LA2LB_1LB0LB0RB never halts.

Usually, some of these block configurations is closed, but with the exception of a few rules that halt. In those cases, further analysis is typically needed.