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 Fixed broken format
Polygon (talk | contribs)
1,849 edits
Added CPS variants
 
(78 intermediate revisions by the same user not shown)
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 BB(4,3) champion.
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)


==Analysis==
<pre>
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]
* [[Repeated Word List]] (RWL_mod; more detailed description for RWLAcc)
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]
== 1RB2LA1RC3RA_1LA2RA2RB0RC_1RZ3LC1RA1RB ==


10. S 2 <D (11)^a 0^2 S --> S <D (11)^a+1 2 S [+4a +7 steps]
{{machine|1RB2LA1RC3RA_1LA2RA2RB0RC_1RZ3LC1RA1RB}
11. S 2 <D (11)^a 2 0^2 S --> S <D (11)^a+1 2^2 S [+4a +7 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


12. S  1^a <A (11)^b 0^2 S --> S 1^a-1 <A (11)^b+1 2 S [+4b +7 steps]
=== Analysis by Shawn Ligocki ===
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]
https://discord.com/channels/960643023006490684/1095740122139480195/1230591736829575282


14. S (12)^a 1 <D (11)^b 0^2 S --> S (12)^a-1 1 <D (11)^b+2 [+4b +8 steps]
<pre>
15. S (12)^a 1 <D (11)^b 0^inf --> S 1 <D (11)^b+2a 0^inf [+4a^2 +4ba + 4a steps]
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
 
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
</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
 
Let <math>f_1(n) = 2^{n+4} \times 3 -5</math>
 
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) --> D(a, b-1, 2^{b+4} \times 3 -5)</math>
* <math>D_1(a, b, c) --> D_1(a, b-1, 2^{b+4} \times 3 -5)</math>
 
Rule 23 becomes:
* <math>D(a, 0, c) --> D(a-3, 2c+11, 1)</math>
* <math>D_1(a, 0, c) --> D_1(a-3, 2c+11, 1)</math>
 
Rule 24 becomes:
* <math>D(0, 0, c) --> D(c+1, 3, 1)</math>
 
Rule 25 becomes:
* <math>D(2, 0, c) --> D(2c+8, 3, 1)</math>
 
Rule 26 becomes:
* <math>D_1(1, 0, c) --> D_1(2c+7, 3, 1)</math>
 
Rule 27 becomes:
* <math>D_1(0, 0, c) --> D(2c+5, 3, 1)</math>
 
Rule 28 becomes:
* D(1, 0, c) --> halt with score 4c + 18
 
Rule 29 becomes:
* <math>D_1(2, 0, c) --> D(2c+10, 2, 1)</math>
 
By repeating rule 21, a stronger rule can be constructed:
* <math>D(a, b, c) --> D(a, 0, f_1^{b}(c))</math>
* <math>D_1(a, b, c) --> D1(a, 0, f_1^{b}(c))</math>
 
If a is greater than or equal to 3:
<math>D(a, 0, c) --> D(a-3, 2c+11, 1) --> D(a-3, 0, f_1^{2c+11}(1))</math>
=<math>D(a-3, 0, f_2(1,c))</math>
* <math>D(a, 0, c) --> D(a-3, 0, f_1^{2c+11}(1))</math>
 
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>:
 
* <math>D(3k+d, 0, c) --> D(d, 0, f_2(k, c))</math>
* <math>D_1(3k+d, 0, c) --> 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>
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)))


<math>e_1 = f_1(91) = 2^{95} \times 3 -5</math>


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


<math>D(2, 0, e_1)</math>
=== References
 
--><math>D_1(2e_1+8, 3, 1) --> 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) --> D_1(2e_2+7, 0, f_1^{2}(91))</math>
 
2e_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) --> 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>

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"