User:Polygon/Page for testing: Difference between revisions

Latest revision as of 18:44, 4 December 2025

{machine|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}} 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.

[Category:BB(6)]]

@@ Line 1: / Line 1: @@
-{{TM|1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_2RB2RA2RD|halt}} is a pentational halting [[BB(4,3)]] TM. It was discovered in May 2024 by Pavel Kropitz as one of seven long running TMs and achieves a score of over <math>2 \uparrow^{4} 5</math>, making it the current BB(4,3) champion. Polygon analysed the TM by hand in October 2025, providing its score.
+{machine|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}}
+{{TM|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}} is a [[BB(6)]] [[holdout]] TM.
-Pavel listed the halting tape as:
+==Analysis==
-<pre>
-Z> 1^((2*<(<(<(16*2^(92) - 3); (24*2^((24*2^(<(b + 10); (24*2^(b) - 4); 2>) - 3)) - 11); (24*2^((24*2^(<(24*2^((24*2^(<(24*2^((24*2^(92) - 3)) - 2); (24*2^(b) - 4); 92>) - 3)) - 1); (24*2^(b) - 4); 2>) - 3)) - 11)> + 8)/3; (24*2^((24*2^(<(b + 10); (24*2^(b) - 4); 2>) - 3)) - 11); (24*2^((24*2^(<1; (24*2^(b) - 4); 2>) - 3)) - 11)> + 5)/3; (24*2^((24*2^(<(b + 10); (24*2^(b) - 4); 2>) - 3)) - 11); (24*2^((24*2^(<1; (24*2^(b) - 4); 2>) - 3)) - 11)> + 19))
-</pre>
-==Analysis by Polygon==
+Early rules:
 <pre>
 S is any tape configuration
-. S D> 2^a S --> S 2^a D> S [+a steps]
-. S B> 1^a S --> S 1^a B> S [+a steps]
-. S A> 0^2 S --> S <A 1^2 S [+5 steps]
-. S D> (11)^a S --> S (21)^a D> S [+2a steps]
-   S A> (11)^a S --> S (12)^a A> S [+2a steps]
-. S (21)^a <C S --> S <C (11)^a S [+2a steps]
-   S (12)^a <A S --> S <A (11)^a S [+2a steps]
-. S (12)^a A> 0^2 S --> S <A (11)^a+1 S [+2a +5 steps]
-. S A> (11)^1 2^b S --> S 2 A> (11)^1 2^b-1 S [+5 steps]
+. S 0^a <B S --> S <B 1^a S [+a steps]
-. S A> (11)^1 2^b S --> S 2^b A> (11)^1 S [+5b steps]
+. S D> 1^2 S --> S 1 D> 1 S [+3 steps]
+. S D> 1^a 1 S --> S 1^a D> 1 S [+3a steps] (if a > 0)
+. S (11)^a <E S --> S <E (11)^a S [+2a steps]
+   S (11)^a <A S --> S <A (11)^a S [+2a steps]
+. S 1^2 D> 1 0 S --> S <E 0 1^3 S [+5 steps]
+. S 0 1^a <E S --> S 1 0 1^a-2 D> 1 S [+4a -4 steps] (if a mod 2 = 0)
+</pre>
-. S D> 0^2 S --> S <B 2^2 S [+3 steps]
+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
-. S 2 <D (11)^a 0^2 S --> S <D (11)^a+1 2 S [+4a +7 steps]
+b mod 2 = 0:
-. S 2 <D (11)^a 2 0^2 S --> S <D (11)^a+1 2^2 S [+4a +7 steps]
+   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.
-. S  1^a <A (11)^b 0^2 S --> S 1^a-1 <A (11)^b+1 2 S [+4b +7 steps]
+'''Accelerated rules:'''
-. S 1^a <A (11)^b 2 0^2 S --> S 1^a-1 <A (11)^b+1 2^2 S [+4b +7 steps]
+<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)
-. S (12)^a 1 <D (11)^b 0^2 S --> S (12)^a-1 1 <D (11)^b+2 [+4b +8 steps]
+A1: A(0, 2k+1, c, ...) --> A(0, 2(k-1)+1, c+6, ...) [+16k +10 steps] (if k ≥ 3)
-. S (12)^a 1 <D (11)^b 0^inf --> S 1 <D (11)^b+2a 0^inf [+4a^2 +4ba + 4a steps]
+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]
-. S (12)^a 2 1 <D (11)^b 0^inf --> S (12)^a-1 2 (12)^b+2 1 <D (11)^1 0^inf [+10b +28 steps]
+A2: A(0, 2k+1, c, ...) --> A(0, 5, c+6k-12) [+8k^2 +18k -68 steps] (if k ≥ 3)
-. S (12)^a 2 1 <D (11)^b 0^inf --> S (12)^a-1 2 1 <D (11)^2b+5 0^inf
+by repetition of rule A1
-. S (12)^a 2 1 <D (11)^b 0^inf --> S 2 1 <D (11)^(2^a)*b+(2^a)*5-5 0^inf
-. S (12)^a 2 1 <D (11)^b 2 0^inf --> S (12)^a 2^2 1 <D (11)^2b-1 0^inf
+A3: A(0, 2k+1, c, ...) --> A(0, c+6k-4, ...) [+8k^2 +36k +3c -65 steps] (if k ≥ 3)
+by:
-. S (12)^a 1 <D (11)^b 2 0^inf --> S (12)^a 2 1 <D (11)^2b-1 0^inf
+A(0, 2k+1, c, ...)
+--> A(0, 5, c+6k-12, ...) by rule A2 [+8k^2 +18k -68]
-. S (12)^a 2^2 1 <D (11)^b 0^inf --> S (12)^a-1 2^2 1 <D (11)^2^(b+4)*3-5 0^inf
+--> A(2, 1, c+6k-9, ...) [8k^2 +18k -49]
+--> A(0, c+6k-4, ...) [+8k^2 +36k + 3c -65]
-. S 1 <D (11)^b 2^2 0^inf --> S 2 (12)^b-1 2 1 <D (11)^1 0^inf
-. S (11)^a 2^2 1 <D (11)^b 0^inf --> S (11)^a-3 (12)^2b+11 2^2 1 <D (11)^1 0^inf
-. 0^inf 2^2 1 <D (11)^c 0^inf --> 0^inf (11)^c+1 (12)^3 2^2 1 <D (11)^1 0^inf
-. 0^inf (11)^2 2^2 1 <D (11)^c 0^inf --> 0^inf 1 (11)^2c+8 (12)^3 2^2 1 <D (11)^1 0^inf
-. 0^inf 1 (11)^1 2^2 1 <D (11)^c 0^inf --> 0^inf 1 (11)^2c+7 (12)^3 2^2 1 <D (11)^1 0^inf
-. 0^inf 1 2^2 1 <D (11)^c 0^inf --> 0^inf (11)^2c+5 (12)^3 2^2 1 <D (11)^1 0^inf
-. 0^inf (11)^1 2^2 1 <D (11)^c 0^inf --> 0^inf 1 Z> 1 (11)^2c+8 0^inf
 </pre>
-Let D(a, b, c) = 0^inf (11)^a (12)^b 2^2 1 <D (11)^c 0^inf
-Let D_1(a, b, c) = 0^inf 1 (11)^a (12)^b 2^2 1 <D (11)^c 0^inf
+'''Using the accelerated rules:'''
-Let <math>f_1(n) = 2^{n+4} \times 3 -5</math>
+<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
-Let <math>f_2(a,b) = f_1^{2 \times f_2(a-1, b) + 11}(1)</math>, where<math>f_2(0, b) = b</math>
-Rule 21 becomes:
-* <math>D(a, b, c)</math> --> <math>D(a, b-1, 2^{b+4} \times 3 -5)</math>
-* <math>D_1(a, b, c)</math> --> <math>D_1(a, b-1, 2^{b+4} \times 3 -5)</math>
-Rule 23 becomes:
-* D(a, 0, c) --> D(a-3, 2c+11, 1)
-* D_1(a, 0, c) --> D_1(a-3, 2c+11, 1)
-Rule 24 becomes:
-* D(0, 0, c) --> D(c+1, 3, 1)
-Rule 25 becomes:
-* D(2, 0, c) --> D(2c+8, 3, 1)
-Rule 26 becomes:
+b mod 2 = 0:
-* D_1(1, 0, c) --> D_1(2c+7, 3, 1)
+   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, ...)
-Rule 27 becomes:
+   b = 0:
-* D_1(0, 0, c) --> D(2c+5, 3, 1)
+      a mod 2 = 0:
+         a ≥ 4: A(a, 0, c, ...) --> A(1, a-4, c+4, ...)
-Rule 28 becomes:
+         a = 2: A(2, 0, c, d, ...) --> A(2, c+2, d, ...)
-* D(1, 0, c) --> halt with score 4c + 18
+         a = 0: unreachable
+      a mod 2 = 1:
-Rule 29 becomes:
+         a ≥ 4: A(a, 0, c, ...) --> A(2, a-4, c+4, ...)
-* D_1(2, 0, c) --> D(2c+10, 2, 1)
+         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, ...)
-By repeating rule 21, a stronger rule can be constructed:
+b mod 2 = 1:
-* <math>D(a, b, c)</math> --> <math>D(a, 0, f_1^{b}(c))</math>
+   b ≥ 3:
-* <math>D_1(a, b, c)</math> --> <math>D_1(a, 0, f_1^{b}(c))</math>
+      a mod 2 = 0:
+         a ≥ 2: A(a, b, c, ...) --> A(1, a-2, b-2, c+3, ...)
-If a is greater than or equal to 3:
+         a = 0:
-<math>D(a, 0, c)</math> --> <math>D(a-3, 2c+11, 1)</math> --> <math>D(a-3, 0, f_1^{2c+11}(1))</math>
+            b ≥ 7: A(0, 2k+1, c, ...) --> A(0, c+6k-4, ...) by rule A3
-=<math>D(a-3, 0, f_2(1,c))</math>
+            b = 5: A(0, b, c, ...) --> A(2, b-4, c+3, ...)
-* <math>D(a, 0, c)</math> --> <math>D(a-3, 0, f_1^{2c+11}(1))</math>
+            b = 3: unreachable
+      a mod 2 = 1:
-This rule can also be repeated, also note that <math>f_1^{2c+11}(1) = f_2(1,c)</math> and <math>f_1^{2 \times f_2(a,b) + 11}(1) = f_2(a+1,b)</math>:
+         a ≥ 2: A(a, b, c, ...) --> A(2, a-2, b-2, c+3, ...)
+         a = 1: unreachable
-* <math>D(3k+d, 0, c)</math> --> <math>D(d, 0, f_2(k, c))</math>
+   b = 1: A(a, 1, c, d, ...) --> A(0, a+c+3, d, ...)
-* <math>D_1(3k+d, 0, c)</math> --> <math>D_1(d, 0, f_2(k, c))</math>
-The TM starts in configuration D(2, 2, 1).
-D(2, 2, 1) -->
-<math>D(2, 0, f_1^{2}(1)) = D(2, 0, f_1(91))</math>
-<math>e_1 = f_1(91) = 2^{95} \times 3 -5</math>
-<pre>
-f_1(n) = 2^(n+4)*3 - 5
-Note that the times three means that this expression of of the form 3k - 5 which can be rewritten as 3(k-1)-2 which can again be rewritten as 3(k-2)+1.
-Next, 3k+1 mod 3 = 1
-So f_1(n) mod 3 = 1
-Thus f_1^a(n) mod 3 = 1
-f_2(a,b) = f_1^(2*f_2(a-1,b)+11)(1)
-Note that f_1^(2*f_2(a-1,b)+11)(1) is also of the form f_1^a(n)
-Thus f_2(a,b) mod 3 = 1
 </pre>
-<math>D(2, 0, e_1)</math>
+The TM starts in configuration A(0, 2, 0) after 7 steps.
---><math>D_1(2e_1+8, 3, 1)</math> --> <math>D_1(2e_1+8, 0, f_1^{2}(91))</math>
-e_1 mod 3 = 1; 2*1 + 8 = 10 --> 10 mod 3 = 1
-<math>D_1(2e_1+8, 0, f_1^{2}(91))</math>
---> <math>D_1(1,0,f_2(\frac{2e_1+7} 3, f_1^{2}(91)))</math>
-<math>e_2 = f_2(\frac{2e_1+7} 3, f_1^{2}(91))</math>
-<math>D_1(1,0,e_3)</math>
-<math>e_2 mod 3 = 1</math>
---> <math>D_1(2e_2+7, 3, 1)</math> --> <math>D_1(2e_2+7, 0, f_1^{2}(91))</math>
-e_3 + 7
-Modulus: 2 + 7 --> 9 mod 3 = 0
---> <math>D_1(0, 0, f_2(\frac{2e_2+7} 3, f_1^{2}(91)))</math>
-<math>e_3 = f_2(\frac{2e_2+7} 3, f_1^{2}(91))</math>
-<math>D_1(0, 0, e_3)</math>
---> <math>D(2e_3+5, 3, 1)</math> --> <math>D(2e_3+5, 0, f_1^{2}(91))</math>
-e_3 mod 3 = 1; 2*1+5 = 7 --> 7 mod 3 = 1
---> <math>D(1, 0, f_2(\frac{2e_3+4} 3, f_1^{2}(91)))</math>
-<math>e_4 = f_2(\frac{2e_3+4} 3, f_1^{2}(91))</math>
-<math>D(1, 0, e_4)</math>
---> halts with score <math>4e_4 + 18</math>.
-This can be bounded by:
-<math>2 \uparrow^{4} 5 < 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow (7.92 \times 10^{28}) < e_4 < \sigma < S < 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow (7.93 \times 10^{28})</math>
+[Category:BB(6)]]

User:Polygon/Page for testing: Difference between revisions

Latest revision as of 18:44, 4 December 2025

Analysis

Navigation menu

Search