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
Added rules
Polygon (talk | contribs)
1,849 edits
Added CPS variants
 
(68 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]
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)))


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
where the last rule repeats forever.
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
</pre>


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]
=== References
 
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>

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"