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
Added overview of new TM
Polygon (talk | contribs)
1,427 edits
Skelet 10 has been created, removed rom missing
Tag: Manual revert
 
(11 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.
List of incomplete pages:
 
* [[Coq-BB5]]
==Analysis==
* [[Finite Automata Reduction]]
 
* [[CTL]]
Early rules:
* [[Irregular Turing Machine]]
<pre>
* [[Meet-in-the-Middle Weighted Finite Automata Reduction (MITMWFAR)]]
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 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"