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
→Analysis: added Permutations
Polygon (talk | contribs)
1,175 edits
Blanked the page
Tags: Blanking Manual revert
 
Line 1: Line 1:
{machine|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}}
{{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, ...)
  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, ...)
</pre>
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:'''
<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, ...) [+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]
</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, ...)
  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, ...)
</pre>
The TM starts in configuration A(0, 2, 0) after 7 steps.
=== Permutations ===
'''Starting in state B'''
<pre>
S=0: 0^inf <B 0^inf
--> spin out
</pre>
'''Starting in state C'''
<pre>
S=0: 0^inf <C 0^inf
S=1: 0^inf 1 D> 0^inf
S=2: 0^inf 1^2 Z> 0^inf
</pre>
'''Starting in state D'''
<pre>
S=0: 0^inf <D 0^inf
S=1: 0^inf 1 Z> 0^inf
</pre>
'''Starting in state E'''
<pre>
S=0: 0^inf <E 0^inf
S=1: 0^inf 1 F> 0^inf
S=2: 0^inf 1 0 A> 0^inf
S=3: 0^inf 1 0 1 B> 0^inf
S=4: 0^inf 1 0 1 <B 1 0^inf
S=5: 0^inf 1 0 <C 1^2 0^inf
S=6: 0^inf 1^2 D> 1^2 0^inf
S=9: 0^inf 1^3 D> 1 0^inf = A(0, 3, 0)
--> Reaches configuration A(0, 3, 0) after 9 steps.
S=24: 0^inf 1^2 0 1 Z> 1^3 0^inf
</pre>
'''Starting in state F'''
<pre>
S=0: 0^inf <F 0^inf
S=1: 0^inf A> 0^inf
--> Equivalent to starting in state A, but started one step earlier.
</pre>
[Category:BB(6)]]

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"