User:Polygon/Page for testing

1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD (bbch) is a BB(6) holdout TM.

Analysis

Early rules:

S is any tape configuration

1. S 0^a <B S --> S <B 1^a S [+a steps]
2. S D> 1^2 S --> S 1 D> 1 S [+3 steps]
3. S D> 1^a 1 S --> S 1^a D> 1 S [+3a steps] (if a > 0)
4. S (11)^a <E S --> S <E (11)^a S [+2a steps]
   S (11)^a <A S --> S <A (11)^a S [+2a steps]
5. S 1^2 D> 1 0 S --> S <E 0 1^3 S [+5 steps]
6. S 0 1^a <E S --> S 1 0 1^a-2 D> 1 S [+4a -4 steps] (if a mod 2 = 0)

Later rules:

Let A(a, b, c, d, e, f, ..., k) = 0^inf 1^a 0 1^b D> 1 0 1^c 0 1^d 0 1^e 0 1^f ... 0 1^k 0^inf

b mod 2 = 0:
   b ≥ 4: A(a, b, c, ...) --> A(a+1, b-4, c+3, ...) by rule 7
   b = 2: A(a, 2, c, d, ...) --> A(a+2, c+1, d, ...) by rule 9
   b = 0:
      a mod 2 = 0:
         a ≥ 4: A(a, 0, c, ...) --> A(1, a-4, c+4, ...) by rule 10
         a = 2: A(2, 0, c, d, ...) --> A(2, c+2, d, ...) by rule 11
         a = 0: A(0, 0, c, ...) --> spin out by rule 12
      a mod 2 = 1:
         a ≥ 4: A(a, 0, c, ...) --> A(2, a-4, c+4, ...) by rule 13
         a = 3: A(3, 0, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+4 ... by rule 14
         a = 1: A(1, 0, c, d, ...) --> A(0, c+4, d, ...) by rule 15
b mod 2 = 1:
   b ≥ 3:
      a mod 2 = 0:
         a ≥ 2: A(a, b, c, ...) --> A(1, a-2, b-2, c+3, ...) by rule 16
         a = 0:
            b ≥ 5: A(0, b, c, ...) --> A(2, b-4, c+3, ...) by rule 17
            b = 3: A(0, 3, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+3 ... by rule 18
      a mod 2 = 1:
         a ≥ 2: A(a, b, c, ...) --> A(2, a-2, b-2, c+3, ...) by rule 19
         a = 1: A(1, b, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^b-2 0 1^c+3 ... by rule 20
   b = 1: A(a, 1, c, d, ...) --> A(0, a+c+3, d, ...) by rule 21

Rules 12, 18 and 20 are not reachable by any of these rules (reaching them would require negative entries), meaning that they can only be triggered if they are the TMs starting configurations.

Accelerated rules:

R8: A(a, 4k+v, c, ...) --> A(a+k, v, c+3k, ...) [+4bk -8k^2 +k steps] (if v mod 2 = 0 and k ≥ 1)

A1: A(0, 2k+1, c, ...) --> A(0, 2(k-1)+1, c+6, ...) [+16k +10 steps] (if k ≥ 3)
by:
A(0, 2k+1, c, ...)
--> A(2, 2(k-2)+1, c+3, ...) by rule 17 [+8k +3]
--> A(1, 0, 2(k-3)+1, c+6, ...) by rule 16 [+10k +10]
--> A(0, 2(k-1)+1, c+6, ...) by rule 15 [+16k +10]

A2: A(0, 2k+1, c, ...) --> A(0, 5, c+6k-12) [+8k^2 +18k -68 steps] (if k ≥ 3)
by repetition of rule A1

A3: A(0, 2k+1, c, ...) --> A(0, c+6k-4, ...) [+8k^2 +36k +3c -65 steps] (if k ≥ 3)
by:
A(0, 2k+1, c, ...)
--> A(0, 5, c+6k-12, ...) by rule A2 [+8k^2 +18k -68]
--> A(2, 1, c+6k-9, ...) by rule 17 [8k^2 +18k -49]
--> A(0, c+6k-4, ...) by rule 21 [+8k^2 +36k + 3c -65]

Using the accelerated rules:

Let A(a, b, c, d, e, f, ..., k) = 0^inf 1^a 0 1^b D> 1 0 1^c 0 1^d 0 1^e 0 1^f ... 0 1^k 0^inf

b mod 2 = 0:
   b ≥ 4: A(a, 4k+v, c, ...) --> A(a+k, v, c+3k, ...) by rule 8
   b = 2: A(a, 2, c, d, ...) --> A(a+2, c+1, d, ...) by rule 9
   b = 0:
      a mod 2 = 0:
         a ≥ 4: A(a, 0, c, ...) --> A(1, a-4, c+4, ...) by rule 10
         a = 2: A(2, 0, c, d, ...) --> A(2, c+2, d, ...) by rule 11
         a = 0: unreachable
      a mod 2 = 1:
         a ≥ 4: A(a, 0, c, ...) --> A(2, a-4, c+4, ...) by rule 13
         a = 3: A(3, 0, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+4 ... by rule 14
         a = 1: A(1, 0, c, d, ...) --> A(0, c+4, d, ...) by rule 15
b mod 2 = 1:
   b ≥ 3:
      a mod 2 = 0:
         a ≥ 2: A(a, b, c, ...) --> A(1, a-2, b-2, c+3, ...) by rule 16
         a = 0:
            b ≥ 7: A(0, 2k+1, c, ...) --> A(0, c+6k-4, ...) by rule A3
            b = 5: A(0, b, c, ...) --> A(2, b-4, c+3, ...) by rule 17
            b = 3: unreachable
      a mod 2 = 1:
         a ≥ 2: A(a, b, c, ...) --> A(2, a-2, b-2, c+3, ...) by rule 19
         a = 1: unreachable
   b = 1: A(a, 1, c, d, ...) --> A(0, a+c+3, d, ...) by rule 21

The TM starts in configuration A(0, 2, 0) after 7 steps.