User:Polygon/Page for testing: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Polygon (talk | contribs)
918 edits
→Analysis by Polygon: Copied in rest of behavior
Polygon (talk | contribs)
918 edits
Blanked the page
Tags: Blanking Manual revert
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{TM|1RB2LB0LB_2LC2LA0LA_2RD1LC1RZ_1RA2LD1RD|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>3 \uparrow\uparrow\uparrow 88574</math>. Polygon analysed the TM by hand in October 2025, providing its score.


Pavel listed the halting tape as:
<pre>
1 Z> 1^(162*3^((3*<(243*3^(6) - 5)/2; (<(54*3^((3b + 11)/2) - 2); (54*3^((3b + 14)/2) - 6); (54*3^(7) - 6)> + 1); (<(54*3^((3*<(54*3^(7) - 3); (54*3^((3b + 14)/2) - 6); (54*3^((81*3^(7) - 2)) - 6)> + 14)/2) - 2); (54*3^((3b + 14)/2) - 6); (54*3^(7) - 6)> + 1)> + 11)/2)) 2
</pre>
== Analysis by [[User:Polygon|Polygon]] ==
<pre>
S is any tape configuration
1. S 1^a <C S --> S <C 1^a S [+a steps]
2. S 1^a <D S --> S <D 2^a S [+a steps]
3. S D> 2^a S --> S 1^a D> S [+a steps]
4. S (11)^a <A S --> S <A (22)^a S [+2a steps]
  S (11)^a <B S --> S <B (22)^a S [+2a steps]
5. 0^inf 2 (11)^a A> (22)^b S --> 0^inf 2 (11)^a+3 A> (22)^b-1 S [+8a +24 steps]
6. 0^inf 2 (11)^a A> (22)^b S --> 0^inf 2 (11)^a+3b A> S
7. 0^inf 2 (11)^a A> 0 (22)^b S --> 0^inf 2 1 (11)^1 A> (22)^a+2 0 (22)^b-1 S [+6a +28 steps]
8. 0^inf 2 (11)^a A> 2 0 2 S --> 0^inf 2 1 (11)^a+3 A> S [+8a +27 steps]
9. 0^inf 2 1 (11)^a A> (22)^b S --> 0^inf 2 1 (11)^3a+4 A> (22)^b-1 S
10. 0^inf 2 1 (11)^a A> (22)^b S --> 0^inf 2 1 (11)^g_1^b(a) A> S
11-1. 0^inf 2 1 (11)^a A> 0 (22)^b S --> 0^inf 2 (11)^3a+4 A> 0 (22)^b-1 2 S
11-2. 0^inf 2 1 (11)^a A> 0 (22)^b S --> 0^inf 2 1 (11)^1 A> (22)^3a+6 0 (22)^b-2 2 S
12. 0^inf 2 (11)^a A> 0 11 S --> 0^inf 2 1 (11)^1 A> 0 (22)^a+2 2 S [+6a +31 steps]
13. 0^inf 2 1 (11)^a A> 0 2^b S --> 0^inf 2 1 (11)^g_2(a) A> 0 2^b-3 S
14. 0^inf 2 1 (11)^a A> 0 2^3k+v S --> 0^inf 2 1 (11)^(g_2)^k(a) A> 0 2^v S
15. 0^inf 2 1 <A S --> 0^inf 1 D> 2^3 S [+8 steps]
16. 0^inf 2 1 (11)^a A> 0 2 1 2 0^inf --> 0^inf 2 1 (11)^1 A> 0 (22)^1 (11)^3a+7 2 0^inf (may be irrelevant)
17. 0^inf 2 1 (11)^a A> 0 (22)^1 1 S --> 0^inf 2 1 (11)^1 A> (22)^3a+6 2 S
18. 0^inf 2 1 (11)^a A> 0 (22)^1 1 S --> 0^inf 2 1 (11)^g_2(a) A> 2 S
19. 0^inf 2 1 (11)^a A> 2 1^3 S --> 0^inf 2 1 (11)^1 A> 0 (22)^3a+5 2 S
19*. 0^inf 2 1 (11)^a A> 2 1^2 S --> 0^inf 1 (11)^3a+5 D> S
19**. 0^inf 2 1 (11)^a A> 2 1 S --> 0^inf <B (22)^3a+4 S
19*** 0^inf 2 1 (11)^a A> 2 S --> 0^inf (11)^3a+3 1 B> S
20. 0^inf 2 1 (11)^a A> 0 (22)^1 1^b S --> 0^inf 2 1 (11)^g_3(a) A> 0 (22)^1 1^b-4 S
21. 0^inf 2 1 (11)^a A> 0 (22)^1 1^4k+v S --> 0^inf 2 1 (11)^g_3^k(a) A> 0 (22)^1 1^v S
22. 0^inf 2 1 (11)^a A> 0 (22)^1 1^3 2 0^inf --> 0^inf 2 1 (11)^1 A> 0 (22)^1 1^6*g_2(a)+12 2 0^inf
23. 0^inf 2 1 (11)^a A> 0 (22)^1 1^2 2 0^inf --> 0^inf 1 Z> (11)^3*g_2(a)+6 2 0^inf
Bonus rules which are not relevant for this TMs behavior:
24. 0^inf (11)^a A> 0 (22)^1 1 2 0^inf --> 0^inf 1 Z> (11)^3*g_2(a)+5 2 0^inf
25. 0^inf 2 1 (11)^a A> 0 (22)^1 2 0^inf --> 0^inf 1 Z> (11)^g_2(a)+1 2 0^inf
</pre>
The following functions were used in these rules:
g_1(n) = 3n + 4
Note that <math>(3^{k}-2) \times 3 + 4 = 3^{k+1} - 2</math>
And 1 = 3^1 - 2
It follows that <math>g_1^{n}(1) = 3^{n+1}-2</math>
<math>g_2(n) = 3^{3n + 7}-2</math>
<math>g_3(n) = g_2^{2 \times (g_2(n)+3)}(1)</math>
Further:
Let L(a,b) = 0^inf 2 1 (11)^a A> 0 (22)^1 1^b 2 0^inf
* L(a,4k+v) --> L(g_3^k(a),v) by rule 21
* L(a,0) --> 0^inf 1 Z> (11)^g_2(a)+1 2 0^inf by rule 25
* L(a,1) --> 0^inf 1 Z> (11)^3*g_2(a)+5 2 0^inf by rule 24
* L(a,2) --> 0^inf 1 Z> (11)^3*g_2(a)+6 2 0^inf by rule 23
* L(a,3) --> L(1,6*g_2(a)+12) by rule 22
The TM reaches configuration L(1,3) after running for 34 steps.
L(1,3) --> L(1,6*g_2(1)+12) by rule 22, this can be simplified to L(1,354294), then:
--> L(g_3^88573(1),2) by rule 21
--> 0^inf 1 Z> <math>(11)^{3 \times (g_2(g_3^{88573}(1)) +6}</math> 2 0^inf by rule 22
So <math>\sigma = 6 \times g_2(g_3^{88573}(1)) + 14</math>.
This can be bunded by:
<math>3 \uparrow\uparrow\uparrow 88574 < \sigma < S < 3 \uparrow\uparrow\uparrow 88575</math>

Latest revision as of 14:15, 19 October 2025

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