BusyBeaverWiki - User contributions [en]

Fractran

2025-11-10T21:37:01Z

Dyuan01: /* Champions */ BBf(0) champion is the empty set

'''Fractran''' (originally styled FRACTRAN) is an esoteric Turing complete model of computation invented by John Conway in 1987.<ref>Conway, John H. (1987). "FRACTRAN: A Simple Universal Programming Language for Arithmetic". ''Open Problems in Communication and Computation''. Springer-Verlag New York, Inc. pp. 4–26. <nowiki>http://doi.org/10.1007/978-1-4612-4808-8_2</nowiki></ref> In this model a program is simply a finite list of fractions, the program state is an integer. For more details see https://en.wikipedia.org/wiki/FRACTRAN

'''BB_fractran'''(n) or '''BBf'''(n) is the Busy Beaver function for Fractran programs.

== Definition ==
A fractran program is a list of rational numbers <math>[q_0, q_1, ... q_{k-1}]</math>called rules and a fractran state is an integer <math>s \in \mathbb{Z}</math>. We say that a rule <math>q_i</math> applies to state <math>s</math> if <math>s \cdot q_i \in \mathbb{Z}</math>. If no rule applies, we say that the computation has halted otherwise we apply the first applicable rule at each step. In that case we say <math>s \to t</math> and <math>t = s \cdot q_i</math> and <math>i = \min \{ i : s \cdot q_i \in \mathbb{Z} \}</math>. We say that a program has runtime N (or halts in N steps) starting in state s if <math>s \to s_1 \to \cdots \to s_N </math> and no rule applies to <math>s_N </math>.

Let <math>\Omega(n)</math> be the total number of prime factors of a positive integer n. In other words <math>\Omega(1) = 0</math> and <math>\Omega(pn) = \Omega(n)</math> for any prime number p. Then given a rule <math>\frac{a}{b} </math> we say that <math>\text{size} \left( \frac{a}{b} \right) = \Omega(a) + \Omega(b) </math>. And the size of a fractran program <math>[q_0, q_1, ... q_{k-1}]</math> is <math>k + \sum_{i=0}^{k-1} \text{size}(q_i) </math>.

BB_fractran(n) or BBf(n) is the maximum runtime starting in state 2 for all halting fractran programs of size n. It is a non-computable function akin to the [[Busy Beaver Functions]] since Fractran is Turing Complete.

== Champions ==
{| class="wikitable"
|+
!n
!BBf(n)
!Example Champion(s)
|-
| 1 || 0 || <code>[]</code>
|-
| 2 || 1 || <code>[1/2]</code>
|-
| 3 || 1 || <code>[3/2]</code>
|-
| 4 || 1 || <code>[9/2]</code>
|-
| 5 || 2 || <code>[3/2, 1/3]</code>
|-
| 6 || 3 || <code>[9/2, 1/3]</code>
|-
| 7 || 4 || <code>[27/2, 1/3]</code>
|-
| 8 || 5 || <code>[81/2, 1/3]</code>
|-
| 9 || 6 || <code>[243/2, 1/3]</code>
|-
| 10 || 7 || <code>[729/2, 1/3]</code>
|-
| 11 || 10 || <code>[27/2, 25/3, 1/5]</code>
|-
| 12 || 13 || <code>[81/2, 25/3, 1/5]</code>
|-
| 13 || 17 || <code>[81/2, 125/3, 1/5]</code>
|-
| 14 || 21 || <code>[243/2, 125/3, 1/5]</code>
|-
| 15 || 28 || <code>[1/45, 4/5, 3/2, 25/3]</code>
|-
| 16 || 53 || <code>[1/45, 4/5, 3/2, 125/3]</code>
|-
| 17 || 107 || <code>[5/6, 49/2, 3/5, 40/7]</code>
|-
| 18 || 211 || <code>[5/6, 49/2, 3/5, 80/7]</code>
|-
| 19 || ≳ 370 || <code>[5/6, 49/2, 3/5, 160/7]</code>
|-
|}

== References ==
<references />

Longitudinal Analysis

2024-11-13T19:44:00Z

Dyuan01: /* Standard Longitudinal Analysis (and Example Proof) */

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:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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:<math display="block">[\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}]</math>

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:<math display="block">[\textrm{<A}^{-1} \; \textrm{B>}] [24] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][24] \rightarrow
[\textrm{<A}^{-1}][\textrm{<A}][44] \rightarrow [44]</math><math display="block">[\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>}]</math><math>[\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
</math>We can modify the first table from our block analysis to get this new table:
{| class="wikitable"
!
![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:
<math display="block">[\$1 \; \textrm{<A}] \rightarrow [\$1][\textrm{<A}] \rightarrow [\$1][\textrm{B>}][4>] \rightarrow
[\$1 \; \textrm{<A}][\textrm{<A}^{-1} \; \textrm{B>}][4>]</math>At the end, you get the full transition table:
{| class="wikitable"
|+
!From
!To
|-
|[$1 <A]
|[$1 <A] [<A^-1 B>] [4>]
|}
{| class="wikitable"
!
![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

<math display="block">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\$]</math>

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 <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> where <math>a_0\leq a_1 \leq a_2\dots </math> and one of the following:

* <math>a_0+1 \geq 3b \;\textrm{and}\; b \geq 1</math> or
* <math>a_0 \geq 3 \; \textrm{and} \; b=0</math>

You can reach a tape of the form <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> 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.
[[Category:Analysis Techniques]]

Longitudinal Analysis

2024-11-13T19:38:40Z

Dyuan01: /* Standard Longitudinal Analysis (and Example Proof) */ added something that hopefully makes the proof I left for the reader easier

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:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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:<math display="block">[\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}]</math>

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:<math display="block">[\textrm{<A}^{-1} \; \textrm{B>}] [24] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][24] \rightarrow
[\textrm{<A}^{-1}][\textrm{<A}][44] \rightarrow [44]</math><math display="block">[\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>}]</math><math>[\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
</math>We can modify the first table from our block analysis to get this new table:
{| class="wikitable"
!
![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:
<math display="block">[\$1 \; \textrm{<A}] \rightarrow [\$1][\textrm{<A}] \rightarrow [\$1][\textrm{B>}][4>] \rightarrow
[\$1 \; \textrm{<A}][\textrm{<A}^{-1} \; \textrm{B>}][4>]</math>At the end, you get the full transition table:
{| class="wikitable"
|+
!From
!To
|-
|[$1 <A]
|[$1 <A] [<A^-1 B>] [4>]
|}
{| class="wikitable"
!
![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

<math display="block">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\$]</math>

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, so 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 <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> where <math>a_0\leq a_1 \leq a_2\dots </math> and one of the following:

* <math>a_0+1 \geq 3b \;\textrm{and}\; b \geq 1</math> or
* <math>a_0 \geq 3 \; \textrm{and} \; b=0</math>

You can reach a tape of the form <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> 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.
[[Category:Analysis Techniques]]

Longitudinal Analysis

2024-11-13T19:35:27Z

Dyuan01: /* Standard Longitudinal Analysis (and Example Proof) */ finished the section

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:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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:<math display="block">[\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}]</math>

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:<math display="block">[\textrm{<A}^{-1} \; \textrm{B>}] [24] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][24] \rightarrow
[\textrm{<A}^{-1}][\textrm{<A}][44] \rightarrow [44]</math><math display="block">[\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>}]</math><math>[\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
</math>We can modify the first table from our block analysis to get this new table:
{| class="wikitable"
!
![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:
<math display="block">[\$1 \; \textrm{<A}] \rightarrow [\$1][\textrm{<A}] \rightarrow [\$1][\textrm{B>}][4>] \rightarrow
[\$1 \; \textrm{<A}][\textrm{<A}^{-1} \; \textrm{B>}][4>]</math>At the end, you get the full transition table:
{| class="wikitable"
|+
!From
!To
|-
|[$1 <A]
|[$1 <A] [<A^-1 B>] [4>]
|}
{| class="wikitable"
!
![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

<math display="block">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\$]</math>

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, so 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) [$]

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

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

Now I will state my inductive claim: Given <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> where <math>a_0\leq a_1 \leq a_2\dots </math> and one of the following:

* <math>a_0+1 \geq 3b \;\textrm{and}\; b \geq 1</math> or
* <math>a_0 \geq 3 \; \textrm{and} \; b=0</math>

You can reach a tape of the form <math>\dots B(a_2) \; B(a_1) \; B(a_0) \; B(b) \; [ \$ ]</math> 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.
[[Category:Analysis Techniques]]

Longitudinal Analysis

2024-11-13T16:36:36Z

Dyuan01: /* Standard Longitudinal Analysis (and Example Proof) */ Added more stuff (still not done yet)

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:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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:<math display="block">[\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}]</math>

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:<math display="block">[\textrm{<A}^{-1} \; \textrm{B>}] [24] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][24] \rightarrow
[\textrm{<A}^{-1}][\textrm{<A}][44] \rightarrow [44]</math><math display="block">[\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>}]</math><math>[\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
</math>We can modify the first table from our block analysis to get this new table:
{| class="wikitable"
!
![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:
<math display="block">[\$1 \; \textrm{<A}] \rightarrow [\$1][\textrm{<A}] \rightarrow [\$1][\textrm{B>}][4>] \rightarrow
[\$1 \; \textrm{<A}][\textrm{<A}^{-1} \; \textrm{B>}][4>]</math>At the end, you get the full transition table:
{| class="wikitable"
|+
!From
!To
|-
|[$1 <A]
|[$1 <A] [<A^-1 B>] [4>]
|}
{| class="wikitable"
!
![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

<math display="block">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\$]</math>

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

== 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.
[[Category:Analysis Techniques]]
[[Category:Stub]]

Longitudinal Analysis

2024-11-13T15:52:07Z

Dyuan01: Edit, but still 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:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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:<math display="block">[\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}]</math>

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:<math display="block">[\textrm{<A}^{-1} \; \textrm{B>}] [24] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][24] \rightarrow
[\textrm{<A}^{-1}][\textrm{<A}][44] \rightarrow [44]</math><math display="block">[\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>}]</math><math>[\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
</math>We can modify the first table from our block analysis to get this new table:
{| class="wikitable"
!
![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:
<math display="block">[\$1 \; \textrm{<A}] \rightarrow [\$1][\textrm{<A}] \rightarrow [\$1][\textrm{B>}][4>] \rightarrow
[\$1 \; \textrm{<A}][\textrm{<A}^{-1} \; \textrm{B>}][4>]</math>At the end, you get the full transition table:
{| class="wikitable"
|+
!From
!To
|-
|[$1 <A]
|[$1 <A] [<A^-1 B>] [4>]
|}
{| class="wikitable"
!
![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

<math display="block">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\$]</math>

So now we have (B(1))^inf [42] [22] [42] [4$]. Now, we can derive these rules:

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 will now show that if we start with B(i) B(j) ([22] or [42] or [44]) and i >= j, then we will end with

== 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.
[[Category:Analysis Techniques]]

Longitudinal Analysis

2024-11-13T15:24:32Z

Dyuan01: Added a point in Warnings and fixed some minor errors.

Longitudinal Analysis

2024-11-10T17:03:25Z

Dyuan01: fixed some grammar errors

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:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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:<math display="block">[\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}]</math>

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:<math display="block">[\textrm{<A}^{-1} \; \textrm{B>}] [24] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][24] \rightarrow
[\textrm{<A}^{-1}][\textrm{<A}][44] \rightarrow [44]</math><math display="block">[\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>}]</math><math>[\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
</math>We can modify the first table from our block analysis to get this new table:
{| class="wikitable"
!
![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:
<math display="block">[\$1 \; \textrm{<A}] \rightarrow [\$1][\textrm{<A}] \rightarrow [\$1][\textrm{B>}][4>] \rightarrow
[\$1 \; \textrm{<A}][\textrm{<A}^{-1} \; \textrm{B>}][4>]</math>At the end, you get the full transition table:
{| class="wikitable"
|+
!From
!To
|-
|[$1 <A]
|[$1 <A] [<A^-1 B>] [4>]
|}
{| class="wikitable"
!
![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 ommitted [<A] from our set of blocks, since we have fully predicted when [<A] arrives.

== Warnings ==
Because we are now able to simulate steps in different orders, there are different rules 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 that 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 will eventually come back as [<A], actually never comes back, either becoming a translated cycler, or for some other reason.
[[Category:Analysis Techniques]]

Longitudinal Analysis

2024-11-10T02:43:57Z

Dyuan01: Changed category

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:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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:<math display="block">[\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}]</math>

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:<math display="block">[\textrm{<A}^{-1} \; \textrm{B>}] [24] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][24] \rightarrow
[\textrm{<A}^{-1}][\textrm{<A}][44] \rightarrow [44]</math><math display="block">[\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>}]</math><math>[\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
</math>We can modify the first table from our block analysis to get this new table:
{| class="wikitable"
!
![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:
<math display="block">[\$1 \; \textrm{<A}] \rightarrow [\$1][\textrm{<A}] \rightarrow [\$1][\textrm{B>}][4>] \rightarrow
[\$1 \; \textrm{<A}][\textrm{<A}^{-1} \; \textrm{B>}][4>]</math>At the end, you get the full transition table:
{| class="wikitable"
|+
!From
!To
|-
|[$1 <A]
|[$1 <A] [<A^-1 B>] [4>]
|}
{| class="wikitable"
!
![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 ommitted [<A] from our set of blocks, since we have fully predicted when [<A] arrives.

== Warnings ==
Because we are now able to simulate steps in different orders, there are different rules 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 that 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 will eventually come back as [<A], it actually never comes back, either becoming a translated cycler, or for some other reason.
[[Category:Analysis Techniques]]

Longitudinal Analysis

2024-11-10T02:43:15Z

Dyuan01: Added more content

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:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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:<math display="block">[\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}]</math>

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:<math display="block">[\textrm{<A}^{-1} \; \textrm{B>}] [24] \rightarrow [\textrm{<A}^{-1}][\textrm{B>}][24] \rightarrow
[\textrm{<A}^{-1}][\textrm{<A}][44] \rightarrow [44]</math><math display="block">[\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>}]</math><math>[\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
</math>We can modify the first table from our block analysis to get this new table:
{| class="wikitable"
!
![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:
<math display="block">[\$1 \; \textrm{<A}] \rightarrow [\$1][\textrm{<A}] \rightarrow [\$1][\textrm{B>}][4>] \rightarrow
[\$1 \; \textrm{<A}][\textrm{<A}^{-1} \; \textrm{B>}][4>]</math>At the end, you get the full transition table:
{| class="wikitable"
|+
!From
!To
|-
|[$1 <A]
|[$1 <A] [<A^-1 B>] [4>]
|}
{| class="wikitable"
!
![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 ommitted [<A] from our set of blocks, since we have fully predicted when [<A] arrives.

== Warnings ==
Because we are now able to simulate steps in different orders, there are different rules 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 that 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 will eventually come back as [<A], it actually never comes back, either becoming a translated cycler, or for some other reason.
[[Category:Stub]]

Longitudinal Analysis

2024-11-09T22:37:20Z

Dyuan01: Added content (still a stub)

Block Analysis

2024-11-08T06:06:41Z

Dyuan01: /* Bonus: Regrouping Symbols */ another minor change

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 <math>0^\infty \; 22212 \; \textrm{ , which can be grouped as follows: <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>. 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:

<math display="block">12 \; \textrm{<B} \; \rightarrow 1 \; \textrm{<B} \; 2 \; \rightarrow \; \textrm{<A} \; 02</math>

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 <math>[\$2] \; [22] \; [\textrm{<A02}] \; [201021\$]</math>. 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:

<math display="block">[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]</math>

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:
{| class="wikitable"
|+
!
![$2]
![12]
![22]
|-
|[<B]
|[$2] [0B>]
|[<A02]
|[<B] [22]
|-
|[<A02]
|[$2] [22] [12] [0B>]
|[<B] [0102]
|[<A02] [12]
|}
{| class="wikitable"
|+
!
![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 <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>, 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:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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 <math>\textrm{ <A } \; 21022 </math>, which can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get <math>1 \; \textrm{ <C } \; 1022</math>, which can be grouped as <math>1 \; [ \textrm{<C} ] \; [1022] </math>. 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:
{| class="wikitable"
!
![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.
[[Category:Analysis Techniques]]

Block Analysis

2024-11-08T06:05:37Z

Dyuan01: /* Bonus: Regrouping Symbols */ made a minor change

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 <math>0^\infty \; 22212 \; \textrm{ , which can be grouped as follows: <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>. 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:

<math display="block">12 \; \textrm{<B} \; \rightarrow 1 \; \textrm{<B} \; 2 \; \rightarrow \; \textrm{<A} \; 02</math>

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 <math>[\$2] \; [22] \; [\textrm{<A02}] \; [201021\$]</math>. 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:

<math display="block">[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]</math>

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:
{| class="wikitable"
|+
!
![$2]
![12]
![22]
|-
|[<B]
|[$2] [0B>]
|[<A02]
|[<B] [22]
|-
|[<A02]
|[$2] [22] [12] [0B>]
|[<B] [0102]
|[<A02] [12]
|}
{| class="wikitable"
|+
!
![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 <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>, 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:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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 <math>\textrm{ <A } \; 21022 </math>, which clearly can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get <math>1 \; \textrm{ <C } \; 1022</math>, which can be grouped as <math>1 \; [ \textrm{<C} ] \; [1022] </math>. 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:
{| class="wikitable"
!
![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.
[[Category:Analysis Techniques]]

Block Analysis

2024-11-08T06:04:40Z

Dyuan01: /* Bonus: Regrouping Symbols */ fixed minor errors

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 <math>0^\infty \; 22212 \; \textrm{ , which can be grouped as follows: <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>. 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:

<math display="block">12 \; \textrm{<B} \; \rightarrow 1 \; \textrm{<B} \; 2 \; \rightarrow \; \textrm{<A} \; 02</math>

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 <math>[\$2] \; [22] \; [\textrm{<A02}] \; [201021\$]</math>. 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:

<math display="block">[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]</math>

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:
{| class="wikitable"
|+
!
![$2]
![12]
![22]
|-
|[<B]
|[$2] [0B>]
|[<A02]
|[<B] [22]
|-
|[<A02]
|[$2] [22] [12] [0B>]
|[<B] [0102]
|[<A02] [12]
|}
{| class="wikitable"
|+
!
![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 <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>, 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 a massive set of blocks that is almost closed: with the exception of a single rule:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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 <math>\textrm{ <A } \; 21022 </math>, which clearly can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get <math>1 \; \textrm{ <C } \; 1022</math>, which can be grouped as <math>1 \; [ \textrm{<C} ] \; [1022] </math>. 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:
{| class="wikitable"
!
![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.
[[Category:Analysis Techniques]]

Block Analysis

2024-11-08T06:00:43Z

Dyuan01: /* Bonus: Regrouping Symbols */ Finished the section

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 <math>0^\infty \; 22212 \; \textrm{ , which can be grouped as follows: <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>. 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:

<math display="block">12 \; \textrm{<B} \; \rightarrow 1 \; \textrm{<B} \; 2 \; \rightarrow \; \textrm{<A} \; 02</math>

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 <math>[\$2] \; [22] \; [\textrm{<A02}] \; [201021\$]</math>. 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:

<math display="block">[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]</math>

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:
{| class="wikitable"
|+
!
![$2]
![12]
![22]
|-
|[<B]
|[$2] [0B>]
|[<A02]
|[<B] [22]
|-
|[<A02]
|[$2] [22] [12] [0B>]
|[<B] [0102]
|[<A02] [12]
|}
{| class="wikitable"
|+
!
![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 <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>, 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 a massive set of blocks that is almost closed: with the exception of a single rule:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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 <math>\textrm{ <A } \; 21022 \;</math>, which clearly can't be regrouped to our previously mentioned blocks. However, if we take one step back, we get <math>1 \; \textrm{ <C } \; 1022</math>, which can be grouped as <math>1 \; [ \textrm{<C} ] \; [1022] \;</math>. The extra 1 can then be regrouped with other blocks with 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:
{| class="wikitable"
!
![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.
[[Category:Analysis Techniques]]

Block Analysis

2024-11-08T05:47:11Z

Dyuan01: /* Bonus: Regroup Symbols */ Added to the new section (still a stub)

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 <math>0^\infty \; 22212 \; \textrm{ , which can be grouped as follows: <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>. 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:

<math display="block">12 \; \textrm{<B} \; \rightarrow 1 \; \textrm{<B} \; 2 \; \rightarrow \; \textrm{<A} \; 02</math>

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 <math>[\$2] \; [22] \; [\textrm{<A02}] \; [201021\$]</math>. 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:

<math display="block">[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]</math>

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:
{| class="wikitable"
|+
!
![$2]
![12]
![22]
|-
|[<B]
|[$2] [0B>]
|[<A02]
|[<B] [22]
|-
|[<A02]
|[$2] [22] [12] [0B>]
|[<B] [0102]
|[<A02] [12]
|}
{| class="wikitable"
|+
!
![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 <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>, 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 a massive set of blocks that is almost closed: with the exception of a single rule:
{| class="wikitable"
|+
!
![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$]
|}
{| class="wikitable"
|+
!
![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>]
|}
[[Category:Analysis Techniques]]
[[Category:Stub]]

Block Analysis

2024-11-08T01:35:36Z

Dyuan01: Added a new section (still a stub)

Analysis Tools and Techniques

2024-11-08T01:33:02Z

Dyuan01:

Note: this is currently a stub

These are either useful tools for analysis or techniques that are used to more easily understand the behavior of TMs. They can be done by hand or by a computer.

* [[Directed Head Notation]]
* [[Block Analysis]]
* [[Inductive Proof]]

[[Category:Stub]]

Analysis Techniques

2024-11-08T01:32:02Z

Dyuan01: Is this how you delete a page?

Analysis Tools and Techniques

2024-11-08T01:30:09Z

Dyuan01: Created page with "Note: this is currently a stub These are techniques that are used to more easily understand the behavior of TMs. They can be done by hand or by a computer. * Directed Head Notation * Block Analysis * Inductive Proof Category:Stub"

Note: this is currently a stub

These are techniques that are used to more easily understand the behavior of TMs. They can be done by hand or by a computer.

* [[Directed Head Notation]]
* [[Block Analysis]]
* [[Inductive Proof]]

[[Category:Stub]]

Block Analysis

2024-11-07T23:51:21Z

Dyuan01: Removed the stub category

Category:Analysis Techniques

2024-11-07T23:49:15Z

Dyuan01: Blanked the page

Category:Analysis Techniques

2024-11-07T23:48:48Z

Block Analysis

2024-11-07T23:47:32Z

Dyuan01: Removed the stub and created a new category "Analysis Techniques"

Block Analysis

2024-11-07T23:46:19Z

Dyuan01: /* Example Proof: 1RB---1LC_2RC0LA2LB_1LB0LB0RB */ Deleted unnecessary section

Note: this is currently a stub

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 <math>0^\infty \; 22212 \; \textrm{ , which can be grouped as follows: <math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>. 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:

<math display="block">12 \; \textrm{<B} \; \rightarrow 1 \; \textrm{<B} \; 2 \; \rightarrow \; \textrm{<A} \; 02</math>

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 <math>[\$2] \; [22] \; [\textrm{<A02}] \; [201021\$]</math>. 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:

<math display="block">[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]</math>

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:
{| class="wikitable"
|+
!
![$2]
![12]
![22]
|-
|[<B]
|[$2] [0B>]
|[<A02]
|[<B] [22]
|-
|[<A02]
|[$2] [22] [12] [0B>]
|[<B] [0102]
|[<A02] [12]
|}
{| class="wikitable"
|+
!
![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<math>[\$2] \; [22] \; [12] \; [\textrm{<B}] \; [201021$]</math>, 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.
[[Category:Stub]]

Block Analysis

2024-11-07T23:45:51Z

Dyuan01: Gave an example of a block analysis

Block Analysis

2024-11-07T22:56:14Z

Dyuan01: Saving the page for now

Note: this is currently a stub

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. We can then create a table of showing the different interactions between the blocks as a whole rather than the individual head and symbols. Blocks can be infinite, containing the infinite string of 0s on either side of the tape, generally represented by a dollar sign ($). They can also contain the head, assuming [[Directed Head Notation]]. Generally the head is always on the outside of the block, pointing outwards.

== Example Proof: 1RB---1LC_2RC0LA2LB_1LB0LB0RB ==
At first glance, it may seem hard to fully grasp the behavior of this TM. But if you look closely, you'll realize that the left half of the tape can be grouped into [$2], [12], and [22], and the right half

Block Analysis

2024-11-07T22:45:33Z

Dyuan01: /* Example: */

Block Analysis

2024-11-07T22:40:58Z

Dyuan01:

Block Analysis

2024-11-07T22:39:10Z

Dyuan01: Created page with "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. We can then create a table of showing the different interactions between the blocks as a whole rather than the individual head and symbols."

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. We can then create a table of showing the different interactions between the blocks as a whole rather than the individual head and symbols.

Analysis Techniques

2024-11-07T22:36:30Z

Dyuan01: Started a page that could be useful for people who want to analyze some TMs

Longitudinal Analysis

2024-11-07T20:25:16Z

Dyuan01: Defined 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, the TM is analyzed cell by cell, starting from one side and analyzing each cell towards the other side. So far, this type of analysis is only effective if we know ahead of time what state is going to meet any cell from one of the two directions.

== Example TM: 1RB4LA1LB2LA0RB_2LB3RB4LA---1RA ==

Skelet 17

2024-07-01T16:18:53Z

Dyuan01: /* TM Behavior */ changed a word

{{machine|1LB---_0RC1LE_0RD1RC_1LA1RB_0LB0LA}}
https://bbchallenge.org/1LB---_0RC1LE_0RD1RC_1LA1RB_0LB0LA

== TM Behavior ==

Skelet 17 can be simulated with the following rules:

<pre>
A(a0, a1, ..., an)=1 (10)^a0 1 (10)^a1 ... 1 (10)^an
</pre>

Skelet 17

2024-07-01T16:17:45Z

Dyuan01: Started the page

{{machine|1LB---_0RC1LE_0RD1RC_1LA1RB_0LB0LA}}
https://bbchallenge.org/1LB---_0RC1LE_0RD1RC_1LA1RB_0LB0LA

== TM Behavior ==

Skelet 17 can be represented with the following rules:

<pre>
A(a0, a1, ..., an)=1 (10)^a0 1 (10)^a1 ... 1 (10)^an
</pre>

1RB1RA 0LC1LE 1LD1LC 1LA0LB 1LF1RE ---0RA

2024-06-28T17:45:13Z

Dyuan01: Added a bullet with the direct tape rules of the TM

{{machine|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}

This machine was the first identified 6-state Collatz-like [[Cryptid]] and it is closely related to [[Hydra]].

On June 28th 2024 on bbchallenge discord server:
* mxdys identifies the machine as a potential [[Cryptid]]:
<pre>
1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA
(0^inf 1^4 0 1^1 0 1^19) A> (1^0 0 0^inf)
(0^inf 1^6 0 1^2 0 1^31) A> (1^0 0 0^inf)
(0^inf 1^5 0 1^1 0 1^52) A> (1^0 0 0^inf)
(0^inf 1^7 0 1^1 0 1^82) A> (1^0 0 0^inf)
(0^inf 1^9 0 1^1 0 1^127) A> (1^0 0 0^inf)
(0^inf 1^11 0 1^2 0 1^193) A> (1^0 0 0^inf)
(0^inf 1^10 0 1^1 0 1^295) A> (1^0 0 0^inf)
(0^inf 1^12 0 1^2 0 1^445) A> (1^0 0 0^inf)
(0^inf 1^11 0 1^1 0 1^673) A> (1^0 0 0^inf)
(0^inf 1^13 0 1^2 0 1^1012) A> (1^0 0 0^inf)
(0^inf 1^12 0 1^2 0 1^1522) A> (1^0 0 0^inf)
(0^inf 1^11 0 1^2 0 1^2287) A> (1^0 0 0^inf)
(0^inf 1^10 0 1^1 0 1^3436) A> (1^0 0 0^inf)
(0^inf 1^12 0 1^1 0 1^5158) A> (1^0 0 0^inf)
(0^inf 1^14 0 1^1 0 1^7741) A> (1^0 0 0^inf)
(0^inf 1^16 0 1^2 0 1^11614) A> (1^0 0 0^inf)
(0^inf 1^15 0 1^2 0 1^17425) A> (1^0 0 0^inf)
(0^inf 1^14 0 1^1 0 1^26143) A> (1^0 0 0^inf)
(0^inf 1^16 0 1^2 0 1^39217) A> (1^0 0 0^inf)
(0^inf 1^15 0 1^1 0 1^58831) A> (1^0 0 0^inf)
(0^inf 1^17 0 1^2 0 1^88249) A> (1^0 0 0^inf)
(0^inf 1^16 0 1^1 0 1^132379) A> (1^0 0 0^inf)
(0^inf 1^18 0 1^2 0 1^198571) A> (1^0 0 0^inf)
(0^inf 1^17 0 1^1 0 1^297862) A> (1^0 0 0^inf)
(0^inf 1^19 0 1^1 0 1^446797) A> (1^0 0 0^inf)
(0^inf 1^21 0 1^2 0 1^670198) A> (1^0 0 0^inf)
This TM looks like a random work like hydra
</pre>

* Then Yto analyses the machine and confirms that the machine is running the [[Hydra]]'s Collatz-like iterated map:
<pre>
f(2n) = 3n
f(2n+1) = 3n+1
</pre>

But iterated from 8 rather than 3 in the case of [[Hydra]] and also, the halting condition is the opposite: this machine halts iff there comes a point where O > 2E with O the number of odd iterates and E the number of even iterates.

* An alternative ruleset for this TM is shown below:
<pre>
A(a+4, b) = 0^inf 1^b 0 1^a E> 0^inf

A(2a, b) -> A(3a, b+2)
A(2a+1, b) -> A(3a+1, b-1), and halt if b=0

Start from A(8, 0)
</pre>

== Review of the result ==
Pending

Shift overflow bouncer counter

2024-06-05T10:53:18Z

Dyuan01: /* Definition */ fixed a minor grammar error

== Definition ==
Shift overflow bouncer counter is an informal class of Turing machines. A typical Turing machine in this class has the following behavior:
* It has both a bouncer and a counter on the tape.
* Increment: when the bouncer finish a loop, the counter is increased by one.
* Overflow: when the counter overflows, the bouncer is reset to nearly empty, and the original location of the bouncer becomes part of the counter (this is imprecise and sometimes it has more complex behavior).

== Examples ==
* [https://bbchallenge.org/1RB0RE_1LC0RA_1LD0LB_1LA0LB_1RF1RA_---0RD&s=60000&ox=0.1 1RB0RE_1LC0RA_1LD0LB_1LA0LB_1RF1RA_---0RD]
* [https://bbchallenge.org/1RB1RE_1LC---_0LD0LC_1RD0RA_1RE0RF_0LA1LD 1RB1RE_1LC---_0LD0LC_1RD0RA_1RE0RF_0LA1LD]
* [https://bbchallenge.org/1RB0RF_1LC1RB_0RD0LB_---0LE_1RE0RA_1RD1RE 1RB0RF_1LC1RB_0RD0LB_---0LE_1RE0RA_1RD1RE]
* [https://bbchallenge.org/1RB3LA3LB1RA3RA_2LA2LB---4RA4LA 1RB3LA3LB1RA3RA_2LA2LB---4RA4LA]