User:Polygon/Page for testing

1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_2RB2RA2RD (bbch) 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 $2\uparrow ^{4}5$, making it the current BB(4,3) champion.

Analysis

S is any tape configuration
1. S D> 2^a S --> S 2^a D> S [+a steps]
2. S B> 1^a S --> S 1^a B> S [+a steps]
3. S A> 0^2 S --> S <A 1^2 S [+5 steps]
4. S D> (11)^a S --> S (21)^a D> S [+2a steps]
   S A> (11)^a S --> S (12)^a A> S [+2a steps]
5. S (21)^a <C S --> S <C (11)^a S [+2a steps]
   S (12)^a <A S --> S <A (11)^a S [+2a steps]
6. S (12)^a A> 0^2 S --> S <A (11)^a+1 S [+2a +5 steps]

7. S A> (11)^1 2^b S --> S 2 A> (11)^1 2^b-1 S [+5 steps]
8. S A> (11)^1 2^b S --> S 2^b A> (11)^1 S [+5b steps]

9. S D> 0^2 S --> S <B 2^2 S [+3 steps]

10. S 2 <D (11)^a 0^2 S --> S <D (11)^a+1 2 S [+4a +7 steps]
11. S 2 <D (11)^a 2 0^2 S --> S <D (11)^a+1 2^2 S [+4a +7 steps]

12. S  1^a <A (11)^b 0^2 S --> S 1^a-1 <A (11)^b+1 2 S [+4b +7 steps]
13. S 1^a <A (11)^b 2 0^2 S --> S 1^a-1 <A (11)^b+1 2^2 S [+4b +7 steps]

14. S (12)^a 1 <D (11)^b 0^2 S --> S (12)^a-1 1 <D (11)^b+2 [+4b +8 steps]
15. S (12)^a 1 <D (11)^b 0^inf --> S 1 <D (11)^b+2a 0^inf [+4a^2 +4ba + 4a steps]

16. 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]
17. S (12)^a 2 1 <D (11)^b 0^inf --> S (12)^a-1 2 1 <D (11)^2b+5 0^inf
18. S (12)^a 2 1 <D (11)^b 0^inf --> S 2 1 <D (11)^(2^a)*b+(2^a)*5-5 0^inf

19. S (12)^a 2 1 <D (11)^b 2 0^inf --> S (12)^a 2^2 1 <D (11)^2b-1 0^inf

20. S (12)^a 1 <D (11)^b 2 0^inf --> S (12)^a 2 1 <D (11)^2b-1 0^inf

21. 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

22. S 1 <D (11)^b 2^2 0^inf --> S 2 (12)^b-1 2 1 <D (11)^1 0^inf

23. 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
24. 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
25. 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
26. 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
27. 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
28. 0^inf (11)^1 2^2 1 <D (11)^c 0^inf --> 0^inf 1 Z> 1 (11)^2c+8 0^inf

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

Let $f_{1}(n)=2^{n+4}\times 3-5$

Let $f_{2}(a,b)=f_{1}^{2\times f_{2}(a-1,b)+11}(1)$, where$f_{2}(0,b)=b$

Rule 21 becomes:

• $D(a,b,c)$ --> $D(a,b-1,2^{b+4}\times 3-5)$
• $D_{1}(a,b,c)$ --> $D_{1}(a,b-1,2^{b+4}\times 3-5)$

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:

• D_1(1, 0, c) --> D_1(2c+7, 3, 1)

Rule 27 becomes:

• D_1(0, 0, c) --> D(2c+5, 3, 1)

Rule 28 becomes:

• D(1, 0, c) --> halt with score 4c + 18

Rule 29 becomes:

• D_1(2, 0, c) --> D(2c+10, 2, 1)

By repeating rule 21, a stronger rule can be constructed:

• $D(a,b,c)$ --> $D(a,0,f_{1}^{b}(c))$
• $D_{1}(a,b,c)$ --> $D_{1}(a,0,f_{1}^{b}(c))$

If a is greater than or equal to 3: $D(a,0,c)$ --> $D(a-3,2c+11,1)$ --> $D(a-3,0,f_{1}^{2c+11}(1))$ =$D(a-3,0,f_{2}(1,c))$

• $D(a,0,c)$ --> $D(a-3,0,f_{1}^{2c+11}(1))$

This rule can also be repeated, also note that $f_{1}^{2c+11}(1)=f_{2}(1,c)$ and $f_{1}^{2\times f_{2}(a,b)+11}(1)=f_{2}(a+1,b)$:

• $D(3k+d,0,c)$ --> $D(d,0,f_{2}(k,c))$
• $D_{1}(3k+d,0,c)$ --> $D_{1}(d,0,f_{2}(k,c))$

The TM starts in configuration D(2, 2, 1).

D(2, 2, 1) -->

$D(2,0,f_{1}^{2}(1))=D(2,0,f_{1}(91))$

$e_{1}=f_{1}(91)=2^{95}\times 3-5$

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

$D(2,0,e_{1})$

-->$D_{1}(2e_{1}+8,3,1)$ --> $D_{1}(2e_{1}+8,0,f_{1}^{2}(91))$

e_1 mod 3 = 1; 2*1 + 8 = 10 --> 10 mod 3 = 1

$D_{1}(2e_{1}+8,0,f_{1}^{2}(91))$

--> $D_{1}(1,0,f_{2}({\frac {2e_{1}+7}{3}},f_{1}^{2}(91)))$

$e_{2}=f_{2}({\frac {2e_{1}+7}{3}},f_{1}^{2}(91))$

$D_{1}(1,0,e_{3})$

$e_{2}mod3=1$

--> $D_{1}(2e_{2}+7,3,1)$ --> $D_{1}(2e_{2}+7,0,f_{1}^{2}(91))$

2e_3 + 7

Modulus: 2 + 7 --> 9 mod 3 = 0

--> $D_{1}(0,0,f_{2}({\frac {2e_{2}+7}{3}},f_{1}^{2}(91)))$

$e_{3}=f_{2}({\frac {2e_{2}+7}{3}},f_{1}^{2}(91))$

$D_{1}(0,0,e_{3})$

--> $D(2e_{3}+5,3,1)$ --> $D(2e_{3}+5,0,f_{1}^{2}(91))$

e_3 mod 3 = 1; 2*1+5 = 7 --> 7 mod 3 = 1

--> $D(1,0,f_{2}({\frac {2e_{3}+4}{3}},f_{1}^{2}(91)))$

$e_{4}=f_{2}({\frac {2e_{3}+4}{3}},f_{1}^{2}(91))$

$D(1,0,e_{4})$

--> halts with score $4e_{4}+18$.

This can be bounded by:

$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})$