User:Polygon/Page for testing

{machine|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}} 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, ...)
   b = 2: A(a, 2, c, d, ...) --> A(a+2, c+1, d, ...)
   b = 0:
      a mod 2 = 0:
         a ≥ 4: A(a, 0, c, ...) --> A(1, a-4, c+4, ...)
         a = 2: A(2, 0, c, d, ...) --> A(2, c+2, d, ...)
         a = 0: A(0, 0, c, ...) --> spin out
      a mod 2 = 1:
         a ≥ 4: A(a, 0, c, ...) --> A(2, a-4, c+4, ...)
         a = 3: A(3, 0, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+4 ...
         a = 1: A(1, 0, c, d, ...) --> A(0, c+4, d, ...)
b mod 2 = 1:
   b ≥ 3:
      a mod 2 = 0:
         a ≥ 2: A(a, b, c, ...) --> A(1, a-2, b-2, c+3, ...)
         a = 0:
            b ≥ 5: A(0, b, c, ...) --> A(2, b-4, c+3, ...)
            b = 3: A(0, 3, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+3 ...
      a mod 2 = 1:
         a ≥ 2: A(a, b, c, ...) --> A(2, a-2, b-2, c+3, ...)
         a = 1: A(1, b, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^b-2 0 1^c+3 ...
   b = 1: A(a, 1, c, d, ...) --> A(0, a+c+3, d, ...)

A(0, 0, c, ...), A(0, 3, c, ...) and A(1, 2k+1, c, ...) 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, ...) [+8k +3]
--> A(1, 0, 2(k-3)+1, c+6, ...) [+10k +10]
--> A(0, 2(k-1)+1, c+6, ...) [+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, ...) [8k^2 +18k -49]
--> A(0, c+6k-4, ...) [+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, ...)
   b = 2: A(a, 2, c, d, ...) --> A(a+2, c+1, d, ...)
   b = 0:
      a mod 2 = 0:
         a ≥ 4: A(a, 0, c, ...) --> A(1, a-4, c+4, ...)
         a = 2: A(2, 0, c, d, ...) --> A(2, c+2, d, ...)
         a = 0: unreachable
      a mod 2 = 1:
         a ≥ 4: A(a, 0, c, ...) --> A(2, a-4, c+4, ...)
         a = 3: A(3, 0, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+4 ...
         a = 1: A(1, 0, c, d, ...) --> A(0, c+4, d, ...)
b mod 2 = 1:
   b ≥ 3:
      a mod 2 = 0:
         a ≥ 2: A(a, b, c, ...) --> A(1, a-2, b-2, c+3, ...)
         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, ...)
            b = 3: unreachable
      a mod 2 = 1:
         a ≥ 2: A(a, b, c, ...) --> A(2, a-2, b-2, c+3, ...)
         a = 1: unreachable
   b = 1: A(a, 1, c, d, ...) --> A(0, a+c+3, d, ...)

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

[Category:BB(6)]]