User:Polygon/Page for testing: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Polygon (talk | contribs)
1,028 edits
Completed trajectory section
Polygon (talk | contribs)
1,028 edits
Removed rule names
 
(90 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{TM|1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA|halt}} is the current [[BB(2,6)]] [[champion]]. It was discovered on the 19th of May 2023 by Pavel Kropitz. It halts with a score > <math>10 \uparrow\uparrow 10 \uparrow\uparrow 10^{10^{115}}</math>.
{{TM|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}} is a [[BB(6)]] [[holdout]] TM.
==Analysis by Shawn Ligocki==
https://www.sligocki.com/2023/05/20/bb-2-6-p3.html
<pre>
Analysis
Level 1
These rules can all be verified by direct simulation:
00 <A 212 22^n 55 → <A 212 22^n+2


00 <A 212 22^n 2 55 → <A 212 55^n+2 2
==Analysis==


0^5 <A 212 22^n 52 5555 → <A 212 55 2 55^n+3 52
Early rules:
00 <A 212 22^n 2 52 5 → <A 212 55^n+2 52
<pre>
S is any tape configuration


Level 2
1. S 0^a <B S --> S <B 1^a S [+a steps]
Repeating the first rule above we get:
2. S D> 1^2 S --> S 1 D> 1 S [+3 steps]
0^∞ <A 212 22^n 55^k → 0^∞ 212 22^n+2k
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>


which let's us prove Rule 2:
Later rules:
0^∞ <A 212 22^n 2 55 → 0^∞ <A 212 55^n+2 2
<pre>
                    → 0^∞ <A 212 22^2n+4 2
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


Level 3
b mod 2 = 0:
Repeating Rule 2 we get:
  b ≥ 4: A(a, b, c, ...) --> A(a+1, b-4, c+3, ...)
0^∞ <A 212 22^n 2 55^k → 0^∞ <A 212 22^(n+4)*((2^k)-4) 2
  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.


which let's us prove Rule 3:
'''Accelerated rules:'''
0^∞ <A 212 22^n 52 5^5 → 0^∞ <A 212 55 2 55^n+3 52 5
<pre>
                      → 0^∞ <A 212 22^2 2 55^n+3 52 5
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)
                      → 0^∞ <A 212 22^(6*2^(n+3)-2) 52 5
                      → 0^∞ <A 212 55^(6*2^(n+3)-2) 52
                      → 0^∞ <A 212 22^(6*2^(n+4)-4) 52


Level 4
A1: A(0, 2k+1, c, ...) --> A(0, 2(k-1)+1, c+6, ...) [+16k +10 steps] (if k ≥ 3)
Let
by:
f(n) = 6*2^(n+4)-4
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]


Repeating Rule 3 we get the Tetration Rule:
A2: A(0, 2k+1, c, ...) --> A(0, 5, c+6k-12) [+8k^2 +18k -68 steps] (if k ≥ 3)
0^∞ <A 212 22^n 52 5^5k → 0^∞ <A 212 22^f^k(n) 52
by repetition of rule A1


This rule will be the main contributor to the score since f^k(n) > 2^^k. In fact, this rule will apply 3 times, which is how we end up with 3 tetrations in the final score (>10^^10^^10^^3).
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>


Halting Trajectory
'''Using the accelerated rules:'''


With these high-level rules, we are now ready to describe the halting trajectory for this TM starting from a blank tape:
<pre>
          191
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
0^∞ <A 0^∞ → 0^∞ <A 212 22^2 52 5^13 2 0^∞


This is our first application of the Tetration Rule. Here calculating the remainder is trivial:
b mod 2 = 0:
A1 = 13 = 5k1 + r1
  b ≥ 4: A(a, 4k+v, c, ...) --> A(a+k, v, c+3k, ...)
r1 = 3
  b = 2: A(a, 2, c, d, ...) --> A(a+2, c+1, d, ...)
k1 = (A1 - r1)/5 = 2
  b = 0:
 
      a mod 2 = 0:
continuing the trajectory:
        a ≥ 4: A(a, 0, c, ...) --> A(1, a-4, c+4, ...)
...→ 0^∞ <A 212 22^f^2(2) 52 5^3 2 0^∞
        a = 2: A(2, 0, c, d, ...) --> A(2, c+2, d, ...)
  → 0^∞ <A 212 55 2 55^f^2(2)+4 2 0^∞
        a = 0: unreachable
  → 0^∞ <A 212 22^2 2 55^f^2(2)+4 2 0^∞
      a mod 2 = 1:
  → 0^∞ <A 212 22^(6*2^(f^2(2)+4)-4) 2 2 0^∞
        a ≥ 4: A(a, 0, c, ...) --> A(2, a-4, c+4, ...)
   = 0^∞ <A 212 22^f^3(2)+1 0^∞
        a = 3: A(3, 0, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+4 ...
  → 0^∞ <A 212 55 52 5^(2*f^3(2)+5) 22 0^∞
        a = 1: A(1, 0, c, d, ...) --> A(0, c+4, d, ...)
  → 0^∞ <A 212 22^2 52 5^(2*f^3(2)+5) 22 0^∞
b mod 2 = 1:
 
   b ≥ 3:
This is our second application of the Tetration Rule. Here calculating the remainder requires using Euler’s totient theorem (as described in BB(6, 2) > 10↑↑15):
      a mod 2 = 0:
A2 = 2*f^3(2)+5 = 5k2 + r2
        a ≥ 2: A(a, b, c, ...) --> A(1, a-2, b-2, c+3, ...)
r2 = 4
        a = 0:
k2 = (A2 - r2)/5 = (2f^3(2)+1)/5
            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>


continuing the trajectory:
The TM starts in configuration A(0, 2, 0) after 7 steps.
...→ 0^∞ <A 212 22^f^k2(2) 52 5^4 22 0^∞
  → 0^∞ <A 212 55 2 55^(f^k2(2))+3 52 22 0^∞
  → 0^∞ <A 212 22^2 2 55^(f^k2(2))+3 52 22 0^∞
  → 0^∞ <A 212 22^(6*(2^(f^k2(2))+3)-4) 2 52 22 0^∞
  → 0^∞ <A 212 55^(6*(2^(f^k2(2))+3)-1) 52 0^∞
  → 0^∞ <A 212 22^(6*(2^(f^k2(2))+4)-2) 52 0^∞
  = 0^∞ <A 212 22^f^k2+1(2)+2 52 0^∞
  → 0^∞ <A 212 55 52 5^(2*(f^k2+1(2))+13) 2 0^∞
  → 0^∞ <A 212 22^2 52 5^(2*(f^k2+1(2))+13) 2 0^∞
 
This is our third and final application of the Tetration Rule. Here calculating the remainder requires a minor arithmetic miracle (see next section):
A3 = 2*f^k2+1(2)+13 = 5k3 + r3
r3 = 2
k3 = (A3 - r3)/5 = (2*f^k2+1(2)+11)/5
 
finishing the trajectory:
0^∞ <A 212 22^f^k3(2) 52 5^2 2 0^∞ → 0^∞ 141 Z> 2^(2*f^k3(2)+8) 152 0^∞
 
And we see that it halts with a score of
Sigma(p3) = 2*f^k3(2)+14
</pre>

Latest revision as of 14:44, 3 November 2025

1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD (bbch) is a BB(6) holdout TM.

Analysis

Early rules: 

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)

Later rules: 

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, ...)

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: 

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]

Using the accelerated rules: 

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, ...)

The TM starts in configuration A(0, 2, 0) after 7 steps.

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