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
Copied in cosearch article about skelet 17
Polygon (talk | contribs)
1,849 edits
Added CPS variants
 
(56 intermediate revisions by the same user not shown)
Line 1: Line 1:
{machine|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}}
List of incomplete pages:
{{TM|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}} is a [[BB(6)]] [[holdout]] TM.
* [[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==


Early rules:
* [[Repeated Word List]] (RWL_mod; more detailed description for RWLAcc)
<pre>
S is any tape configuration


1. S 0^a <B S --> S <B 1^a S [+a steps]
== 1RB2LA1RC3RA_1LA2RA2RB0RC_1RZ3LC1RA1RB ==
2. S D> 1^2 S --> S 1 D> 1 S [+3 steps]
3. S D> 1^a 1 S --> S 1^a D> 1 S [+3a steps] (if a > 0)
4. S (11)^a <E S --> S <E (11)^a S [+2a steps]
  S (11)^a <A S --> S <A (11)^a S [+2a steps]
5. S 1^2 D> 1 0 S --> S <E 0 1^3 S [+5 steps]
6. S 0 1^a <E S --> S 1 0 1^a-2 D> 1 S [+4a -4 steps] (if a mod 2 = 0)
</pre>


Later rules:
{{machine|1RB2LA1RC3RA_1LA2RA2RB0RC_1RZ3LC1RA1RB}
<pre>
{{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
Let A(a, b, c, d, e, f, ..., k) = 0^inf 1^a 0 1^b D> 1 0 1^c 0 1^d 0 1^e 0 1^f ... 0 1^k 0^inf


b mod 2 = 0:
=== Analysis by Shawn Ligocki ===
  b ≥ 4: A(a, b, c, ...) --> A(a+1, b-4, c+3, ...)
https://discord.com/channels/960643023006490684/1095740122139480195/1230591736829575282
  b = 2: A(a, 2, c, d, ...) --> A(a+2, c+1, d, ...)
  b = 0:
      a mod 2 = 0:
        a ≥ 4: A(a, 0, c, ...) --> A(1, a-4, c+4, ...)
        a = 2: A(2, 0, c, d, ...) --> A(2, c+2, d, ...)
        a = 0: A(0, 0, c, ...) --> spin out
      a mod 2 = 1:
        a ≥ 4: A(a, 0, c, ...) --> A(2, a-4, c+4, ...)
        a = 3: A(3, 0, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+4 ...
        a = 1: A(1, 0, c, d, ...) --> A(0, c+4, d, ...)
b mod 2 = 1:
  b ≥ 3:
      a mod 2 = 0:
        a ≥ 2: A(a, b, c, ...) --> A(1, a-2, b-2, c+3, ...)
        a = 0:
            b ≥ 5: A(0, b, c, ...) --> A(2, b-4, c+3, ...)
            b = 3: A(0, 3, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+3 ...
      a mod 2 = 1:
        a ≥ 2: A(a, b, c, ...) --> A(2, a-2, b-2, c+3, ...)
        a = 1: A(1, b, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^b-2 0 1^c+3 ...
  b = 1: A(a, 1, c, d, ...) --> A(0, a+c+3, d, ...)
</pre>
A(0, 0, c, ...), A(0, 3, c, ...) and A(1, 2k+1, c, ...) are not reachable by any of these rules (reaching them would require negative entries), meaning that they can only be triggered if they are the TMs starting configurations.


'''Accelerated rules:'''
<pre>
<pre>
R8: A(a, 4k+v, c, ...) --> A(a+k, v, c+3k, ...) [+4bk -8k^2 +k steps] (if v mod 2 = 0 and k ≥ 1)
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
 
A1: A(0, 2k+1, c, ...) --> A(0, 2(k-1)+1, c+6, ...) [+16k +10 steps] (if k ≥ 3)
by:
A(0, 2k+1, c, ...)
--> A(2, 2(k-2)+1, c+3, ...) [+8k +3]
--> A(1, 0, 2(k-3)+1, c+6, ...) [+10k +10]
--> A(0, 2(k-1)+1, c+6, ...) [+16k +10]
 
A2: A(0, 2k+1, c, ...) --> A(0, 5, c+6k-12) [+8k^2 +18k -68 steps] (if k ≥ 3)
by repetition of rule A1
 
A3: A(0, 2k+1, c, ...) --> A(0, c+6k-4, ...) [+8k^2 +36k +3c -65 steps] (if k ≥ 3)
by:
A(0, 2k+1, c, ...)
--> A(0, 5, c+6k-12, ...) by rule A2 [+8k^2 +18k -68]
--> A(2, 1, c+6k-9, ...) [8k^2 +18k -49]
--> A(0, c+6k-4, ...) [+8k^2 +36k + 3c -65]
</pre>


'''Using the accelerated rules:'''
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)))


<pre>
Let A(a, b, c, d, e, f, ..., k) = 0^inf 1^a 0 1^b D> 1 0 1^c 0 1^d 0 1^e 0 1^f ... 0 1^k 0^inf


b mod 2 = 0:
where the last rule repeats forever.
  b ≥ 4: A(a, 4k+v, c, ...) --> A(a+k, v, c+3k, ...)
  b = 2: A(a, 2, c, d, ...) --> A(a+2, c+1, d, ...)
  b = 0:
      a mod 2 = 0:
        a ≥ 4: A(a, 0, c, ...) --> A(1, a-4, c+4, ...)
        a = 2: A(2, 0, c, d, ...) --> A(2, c+2, d, ...)
        a = 0: unreachable
      a mod 2 = 1:
        a ≥ 4: A(a, 0, c, ...) --> A(2, a-4, c+4, ...)
        a = 3: A(3, 0, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+4 ...
        a = 1: A(1, 0, c, d, ...) --> A(0, c+4, d, ...)
b mod 2 = 1:
  b ≥ 3:
      a mod 2 = 0:
        a ≥ 2: A(a, b, c, ...) --> A(1, a-2, b-2, c+3, ...)
        a = 0:
            b ≥ 7: A(0, 2k+1, c, ...) --> A(0, c+6k-4, ...) by rule A3
            b = 5: A(0, b, c, ...) --> A(2, b-4, c+3, ...)
            b = 3: unreachable
      a mod 2 = 1:
        a ≥ 2: A(a, b, c, ...) --> A(2, a-2, b-2, c+3, ...)
        a = 1: unreachable
  b = 1: A(a, 1, c, d, ...) --> A(0, a+c+3, d, ...)
</pre>
</pre>


The TM starts in configuration A(0, 2, 0) after 7 steps.
=== References
 
[Category:BB(6)]]
 
-----
Skelet 17
 
Featured Links
 
Chat about it https://discord.com/channels/960643023006490684/1082035052961091705
 
Highlighted message https://discord.com/channels/960643023006490684/1082035052961091705/1269022847502647357
 
Description
 
It looks like Skelet 17 is not CTL-able, then. Consider a list like [a, b, c, ... k, z] (assume z is even). It can be converted to something like [something dependent on a to k] <B 10^z. As it turns out, if we artificially make z sufficiently large, the gray counter will eventually reach 0 before ever switching directions and eventually halt. On the flip side, there is no limit to how large the last element can be in the forward behavior of Skelet 17. So by always selecting the next A_n <B B_n to be the one such that z is large enough to make A_m <B 10^z halt for all m < n, we have constructed an infinite sequence such that A_n <B B_n are all visited, but A_m <B B_n halt for m < n.

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"