User:Polygon/Page for testing: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Polygon (talk | contribs)
1,261 edits
Copied in cosearch article about skelet 17
Polygon (talk | contribs)
1,261 edits
Blanked the page
Tags: Blanking Manual revert
 
(2 intermediate revisions by the same user not shown)
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.
[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.

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"