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.

Bonus: Regrouping Symbols

Sometimes, a few block interactions can almost be closed with the exception of an extra symbol that messes everything up. One solution is to make that symbol its own block, which may end up multiplying the number of blocks you have to deal with. Another way to deal with this is to regroup the extra symbol with the rest of the tape.

Take the TM 1RB2LB0LC_2LA2RA1RB_---2LA1LC for example. There is the following set of blocks that is almost closed: with the exception of a single rule:

	[102]	[1102]	[1022]	[10202]	[11022]	[10222]	[110202]	[102202]	[102$]	[1102$]	[1022$]
[B>]	[211] [B>]	[<C] [1022]	[2111] [B>]	[<C] [11022]	[<C] [10222]	[21111] [B>]	[<C] [102202]	[<C02] [1022]	[<C] [1102$]	[<C] [1022$]	[<C02] [102$]

	[211]	[111]	[2111]	[21111]	[$11]	[$1111]
[<C]	[111] [B>]	[<C] [102]	[<C] [1022]	[<C02] [102]	[$1111] [B>]	[$11] [211] [B>]
[<C02]	???	[<C] [10202]	[<C] [102202]	[<C02] [10202]	[$1111] [2111] [B>]	[$11] [211] [21111] [B>]

The only interaction left is [211] [<C02]. Simulating this gives us ${\textrm {<A}}\;21022$, which can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get $1\;{\textrm {<C}}\;1022$, which can be grouped as $1\;[{\textrm {<C}}]\;[1022]$. The extra 1 can then be regrouped with other blocks on the left. Let's denote 1 as [<1] with the arrow indicating that it will try to regroup with blocks on the left. This completes our second table:

	[211]	[111]	[2111]	[21111]	[$11]	[$111]	[$1111]
[<C]	[111] [B>]	[<C] [102]	[<C] [1022]	[<C02] [102]	[$1111] [B>]	Halt	[$11] [211] [B>]
[<C02]	[<1] [<C] [1022]	[<C] [10202]	[<C] [102202]	[<C02] [10202]	[$1111] [2111] [B>]	Halt	[$11] [211] [21111] [B>]
[<1]	[2111]	[<1] [111]	[21111]	[211] [111]	[$111]	[$1111]	[$11] [111]

Note that the interaction [<1] [<C] is undefined, so you would have to combine the [<1] with the block to its left before proceeding. Also note the newly introduced halting interactions, meaning further analysis is needed to solve this TM.