User:Polygon/Page for testing: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Polygon (talk | contribs)
1,427 edits
Copied in cosearch article about skelet 17
Polygon (talk | contribs)
1,427 edits
Skelet 10 has been created, removed rom missing
Tag: Manual revert
 
(8 intermediate revisions by the same user not shown)
Line 1: Line 1:
{machine|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}}
List of incomplete pages:
{{TM|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}} is a [[BB(6)]] [[holdout]] TM.
* [[Coq-BB5]]
 
* [[Finite Automata Reduction]]
==Analysis==
* [[CTL]]
 
* [[Irregular Turing Machine]]
Early rules:
* [[Meet-in-the-Middle Weighted Finite Automata Reduction (MITMWFAR)]]
<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 16:46, 21 February 2026

List of incomplete pages:

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