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 overview of new TM
Polygon (talk | contribs)
1,849 edits
Added CPS variants
 
(59 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{TM|1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD}} is a [[BB(6)]] [[holdout]] TM.
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==


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, ...) by rule 7
https://discord.com/channels/960643023006490684/1095740122139480195/1230591736829575282
  b = 2: A(a, 2, c, d, ...) --> A(a+2, c+1, d, ...) by rule 9
  b = 0:
      a mod 2 = 0:
        a ≥ 4: A(a, 0, c, ...) --> A(1, a-4, c+4, ...) by rule 10
        a = 2: A(2, 0, c, d, ...) --> A(2, c+2, d, ...) by rule 11
        a = 0: A(0, 0, c, ...) --> spin out by rule 12
      a mod 2 = 1:
        a ≥ 4: A(a, 0, c, ...) --> A(2, a-4, c+4, ...) by rule 13
        a = 3: A(3, 0, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+4 ... by rule 14
        a = 1: A(1, 0, c, d, ...) --> A(0, c+4, d, ...) by rule 15
b mod 2 = 1:
  b ≥ 3:
      a mod 2 = 0:
        a ≥ 2: A(a, b, c, ...) --> A(1, a-2, b-2, c+3, ...) by rule 16
        a = 0:
            b ≥ 5: A(0, b, c, ...) --> A(2, b-4, c+3, ...) by rule 17
            b = 3: A(0, 3, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+3 ... by rule 18
      a mod 2 = 1:
        a ≥ 2: A(a, b, c, ...) --> A(2, a-2, b-2, c+3, ...) by rule 19
        a = 1: A(1, b, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^b-2 0 1^c+3 ... by rule 20
  b = 1: A(a, 1, c, d, ...) --> A(0, a+c+3, d, ...) by rule 21
</pre>
Rules 12, 18 and 20 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)
Level 1: D(a, b, c, 2k+r, e) -> D(a, b, c, r, e+2k)
by:
Level 2: D(a, b, c, 1, e) ->  D(a, b, 0, 1, f2(c, e))
A(0, 2k+1, c, ...)
  where f2(c, e) = rep(λx -> 2x+5, c)(e) ~= 2^c
--> A(2, 2(k-2)+1, c+3, ...) by rule 17 [+8k +3]
Level 3: D(a, b, 0, 1, e)  ->  D(a, 0, 0, 1, f3(b, e))
--> A(1, 0, 2(k-3)+1, c+6, ...) by rule 16 [+10k +10]
  where f3(b, e) = rep(λx -> f2(x+2, 1), b)(e)  ~= 2^^b
--> A(0, 2(k-1)+1, c+6, ...) by rule 15 [+16k +10]
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)))


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, ...) by rule 17 [8k^2 +18k -49]
--> A(0, c+6k-4, ...) by rule 21 [+8k^2 +36k + 3c -65]
</pre>
'''Using the accelerated rules:'''
<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, ...) by rule 8
  b = 2: A(a, 2, c, d, ...) --> A(a+2, c+1, d, ...) by rule 9
  b = 0:
      a mod 2 = 0:
        a ≥ 4: A(a, 0, c, ...) --> A(1, a-4, c+4, ...) by rule 10
        a = 2: A(2, 0, c, d, ...) --> A(2, c+2, d, ...) by rule 11
        a = 0: unreachable
      a mod 2 = 1:
        a ≥ 4: A(a, 0, c, ...) --> A(2, a-4, c+4, ...) by rule 13
        a = 3: A(3, 0, c, ...) --> halt with 0^inf 1^2 0 1 Z> 1^c+4 ... by rule 14
        a = 1: A(1, 0, c, d, ...) --> A(0, c+4, d, ...) by rule 15
b mod 2 = 1:
  b ≥ 3:
      a mod 2 = 0:
        a ≥ 2: A(a, b, c, ...) --> A(1, a-2, b-2, c+3, ...) by rule 16
        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, ...) by rule 17
            b = 3: unreachable
      a mod 2 = 1:
        a ≥ 2: A(a, b, c, ...) --> A(2, a-2, b-2, c+3, ...) by rule 19
        a = 1: unreachable
  b = 1: A(a, 1, c, d, ...) --> A(0, a+c+3, d, ...) by rule 21
</pre>
</pre>


The TM starts in configuration A(0, 2, 0) after 7 steps.
=== 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"