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)]]

---

Skelet 17

Featured Links

Chat about it https://discord.com/channels/960643023006490684/1082035052961091705

Highlighted message https://discord.com/channels/960643023006490684/1082035052961091705/1269022847502647357

Description

It looks like Skelet 17 is not CTL-able, then. Consider a list like [a, b, c, ... k, z] (assume z is even). It can be converted to something like [something dependent on a to k] <B 10^z. As it turns out, if we artificially make z sufficiently large, the gray counter will eventually reach 0 before ever switching directions and eventually halt. On the flip side, there is no limit to how large the last element can be in the forward behavior of Skelet 17. So by always selecting the next A_n <B B_n to be the one such that z is large enough to make A_m <B 10^z halt for all m < n, we have constructed an infinite sequence such that A_n <B B_n are all visited, but A_m <B B_n halt for m < n.