User:Polygon/Page for testing: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Polygon (talk | contribs)
1,849 edits
m →Analysis by Polygon: Some formatting changes for visual improvement
Polygon (talk | contribs)
1,849 edits
Added CPS variants
 
(65 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.
List of incomplete pages:
* [[Coq-BB5]]
* [[Finite Automata Reduction]]
* [[CTL]]
* [[Irregular Turing Machine]]
* [[Meet-in-the-Middle Weighted Finite Automata Reduction (MITMWFAR)]]
* [[Skelet 1]]
* [[CPS]] (CPS_LRU, CPS_LRUH)


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]] ==
* [[Repeated Word List]] (RWL_mod; more detailed description for RWLAcc)
<pre>
S is any tape configuration


1. S 1^a <C S --> S <C 1^a S [+a steps]
== 1RB2LA1RC3RA_1LA2RA2RB0RC_1RZ3LC1RA1RB ==
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]
{{machine|1RB2LA1RC3RA_1LA2RA2RB0RC_1RZ3LC1RA1RB}
  S (11)^a <B S --> S <B (22)^a S [+2a steps]
{{TM|1RB2LA1RC3RA_1LA2RA2RB0RC_1RZ3LC1RA1RB} is a non-halting [[BB(4,3)]] TM discovered by Pavel Kropitz in May 2023.<ref>https://discord.com/channels/960643023006490684/1095740122139480195/1113545691994783804</ref In April 2024, Shawn Ligocki showed the TM to follow an infinite pentational rule, proving it non-halting.<ref>https://discord.com/channels/960643023006490684/1095740122139480195/1230591736829575282</ref


5. 0^inf 2 (11)^a A> (22)^b S --> 0^inf 2 (11)^a+3 A> (22)^b-1 S [+8a +24 steps]
=== Analysis by Shawn Ligocki ===
6. 0^inf 2 (11)^a A> (22)^b S --> 0^inf 2 (11)^a+3b A> S
https://discord.com/channels/960643023006490684/1095740122139480195/1230591736829575282


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]
<pre>
 
Let D(a, b, c, d, e) = 0^inf 1 2^a 1 3^b 1 01^c 1 2^d <A 2^2e+1 0^inf
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:


<math>g_1(n) = 3n + 4</math>
Level 1: D(a, b, c, 2k+r, e)  ->  D(a, b, c, r, e+2k)
Level 2: D(a, b, c, 1, e)  ->  D(a, b, 0, 1, f2(c, e))
  where f2(c, e) = rep(λx -> 2x+5, c)(e) ~= 2^c
Level 3: D(a, b, 0, 1, e)  ->  D(a, 0, 0, 1, f3(b, e))
  where f3(b, e) = rep(λx -> f2(x+2, 1), b)(e)  ~= 2^^b
Level 4: D(2a+r, 0, 0, 1, e)  -> D(r, 0, 0, 1, f4(a, e))
  where f4(a, e) = rep(λx -> f3(2x+7), a)(e)  ~= 2^^^a
Level 5: D(0, 0, 0, 1, e)  ->  D(0, 0, 0, 1, f4(4e+19, f3(1, 1)))


Note that <math>(3^{k}-2) \times 3 + 4 = 3^{k+1} - 2</math>


And <math>1 = 3^1 - 2</math>
where the last rule repeats forever.
 
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>
<pre>
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.
</pre>
</pre>
L(1, 3) --> <math>L(1, 6*g_2(1) + 12)</math> by rule 22, this can be simplified to L(1, 354294), then:
--> <math>L(g_3^{88573}(1),2)</math> 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>
=== References

Latest revision as of 10:46, 3 April 2026

List of incomplete pages:


1RB2LA1RC3RA_1LA2RA2RB0RC_1RZ3LC1RA1RB

{{machine|1RB2LA1RC3RA_1LA2RA2RB0RC_1RZ3LC1RA1RB} {{TM|1RB2LA1RC3RA_1LA2RA2RB0RC_1RZ3LC1RA1RB} is a non-halting BB(4,3) TM discovered by Pavel Kropitz in May 2023.<ref>https://discord.com/channels/960643023006490684/1095740122139480195/1113545691994783804</ref In April 2024, Shawn Ligocki showed the TM to follow an infinite pentational rule, proving it non-halting.<ref>https://discord.com/channels/960643023006490684/1095740122139480195/1230591736829575282</ref

Analysis by Shawn Ligocki

https://discord.com/channels/960643023006490684/1095740122139480195/1230591736829575282 

Let D(a, b, c, d, e) = 0^inf 1 2^a 1 3^b 1 01^c 1 2^d <A 2^2e+1 0^inf

Level 1: D(a, b, c, 2k+r, e)  ->  D(a, b, c, r, e+2k)
Level 2: D(a, b, c, 1, e)  ->  D(a, b, 0, 1, f2(c, e))
  where f2(c, e) = rep(λx -> 2x+5, c)(e)  ~= 2^c
Level 3: D(a, b, 0, 1, e)  ->  D(a, 0, 0, 1, f3(b, e))
  where f3(b, e) = rep(λx -> f2(x+2, 1), b)(e)  ~= 2^^b
Level 4: D(2a+r, 0, 0, 1, e)  ->  D(r, 0, 0, 1, f4(a, e))
  where f4(a, e) = rep(λx -> f3(2x+7), a)(e)  ~= 2^^^a
Level 5: D(0, 0, 0, 1, e)  ->  D(0, 0, 0, 1, f4(4e+19, f3(1, 1)))


where the last rule repeats forever.

=== References

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