User:Polygon/Page for testing: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Polygon (talk | contribs)
1,175 edits
Added overview of new TM
Polygon (talk | contribs)
1,175 edits
Blanked the page
Tags: Blanking Manual revert
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{TM|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}} is a [[BB(6)]] [[holdout]] TM.


==Analysis==
Early rules:
<pre>
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)
</pre>
Later rules:
<pre>
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
</pre>
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:'''
<pre>
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]
</pre>
'''Using the accelerated rules:'''
<pre>
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
</pre>
The TM starts in configuration A(0, 2, 0) after 7 steps.

Latest revision as of 23:18, 26 December 2025

Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=User:Polygon/Page_for_testing&oldid=5804"