1RB1LD 1RC1RB 1LC1LA 0RC0RD: Difference between revisions

Latest revision as of 16:54, 3 August 2026

1RB1LD_1RC1RB_1LC1LA_0RC0RD (bbch) is the current Blanking Busy Beaver BLB(4,2) and Beeping Busy Beaver BBB(4,2) champion, creating a blank tape after 32,779,477 steps and quasihalting after 32,779,478 steps at which point it becomes a translated cycler with period 1. It was discovered and reported by Nick Drozd in 2021.^[1]

In 2026, this machine was proven in Rocq to be the BBB(4) winner when considering beep states.^[2]

Analysis by Shawn Ligocki

Let $D (a, b) : = 0^{\infty} 1^{a} 0^{b} D > 0^{\infty}$ then: $\begin{array}{lc} D (a + 3, & b) & \to & D (a, b + 5) \\ D (0, & b) & \to & Blank \\ D (1, & b) & \to & D (b + 2, 4) \\ D (2, & b) & \to & D (b + 3, 4) \end{array}$ let $D (a) : = D (a, 4)$ , then we can simplify to:

$\begin{array}{lc} D (3 k) & \to & Blank \\ D (3 k + 1) & \to & D (5 k + 6) \\ D (3 k + 2) & \to & D (5 k + 7) \end{array}$ Starting from $D (2)$ (at step 19) we get the trajectory:

$\begin{array}{l} D (2) & \to & D (7) & \to & D (16) & \to & D (31) & \to & D (56) & \to & D (97) \\ \to & D (166) & \to & D (281) & \to & D (472) & \to & D (791) & \to & D (1322) \\ \to & D (2207) & \to & D (3682) & \to & D (6141) & \to & Blank \end{array}$ which has the remarkable luck of applying this Collatz-like map 14 times before reaching the blanking config (expected # of applications before halting is 3).

See also, previous analysis in 2021: https://www.sligocki.com/2021/07/17/bb-collatz.html

Relation to other machines

The map and trajectory are equivalent to that of the BB(5) champion. For all $k$ , let $f (k)$ be the number such that $D (k) \to D (f (k))$ , or $HALT$ if $D (k) \to Blank$ , and let $g$ be the map simulated by the BB(5) champion. Then:

$\begin{array}{lc} g (2 (3 k) + 2) & = & g (6 k + 2) & = & HALT & = & f (3 k) \\ g (2 (3 k + 1) + 2) & = & g (6 k + 4) & = & 10 k + 14 & = & 2 f (3 k + 1) + 2 \\ g (2 (3 k + 2) + 2) & = & g (6 k + 6) & = & 10 k + 16 & = & 2 f (3 k + 2) + 2 \end{array}$

So the size of this machine's BLB output is tied to the size of the BB(5) champion's output.

References

↑ Nick Drozd. A New Record in Self-Cleaning Turing Machines. 2021.
↑ Coq-BBB4

[1] Nick Drozd. A New Record in Self-Cleaning Turing Machines. 2021.

[:Coq-BBB4-2] Coq-BBB4

[1]

[2]

@@ Line 1: / Line 1: @@
 {{machine|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}
-{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Blanking Beaver]] BLB(4,2) and [[Beeping Busy Beaver]] BBB(4,2) champion, creating a blank tape after 32,779,477 steps and [[Quasihalt|quasihalting]] after 32,779,478 steps. It is also a [[translated cycler]] with a preperiod of 32,779,478 steps, a period length of 1 step and a cycle offset of 1 to the left. It was discovered and reported by Nick Drozd in 2021.<ref>Nick Drozd. [https://nickdrozd.github.io/2021/07/11/self-cleaning-turing-machine.html A New Record in Self-Cleaning Turing Machines]. 2021.</ref>
+{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Blanking Busy Beaver]] BLB(4,2) and [[Beeping Busy Beaver]] BBB(4,2) champion, creating a blank tape after 32,779,477 steps and [[Quasihalt|quasihalting]] after 32,779,478 steps at which point it becomes a [[translated cycler]] with period 1. It was discovered and reported by Nick Drozd in 2021.<ref>Nick Drozd. [https://nickdrozd.github.io/2021/07/11/self-cleaning-turing-machine.html A New Record in Self-Cleaning Turing Machines]. 2021.</ref>
+In 2026, this machine was proven in Rocq to be the BBB(4) winner when considering beep states.<ref name=":Coq-BBB4">[https://github.com/carrino/Coq-BBB4 Coq-BBB4]</ref>
 == Analysis by [[User:sligocki|Shawn Ligocki]] ==
-Let <math display="block">D(a, b) = 0^\infty \; 1^a \; 0^b \; \textrm{D>} \; 0^\infty</math>then:<math display="block">\begin{array}{lc}
+Let <math display="block">D(a, b):= 0^\infty\;1^a\;0^b\;\textrm{D}\textrm{>}\;0^\infty</math>then:<math display="block">\begin{array}{lc}
    D(a+3, & b) & \to & D(a, b+5) \\
-   D(0, & b) & = & \textrm{Blank} \\
+   D(0, & b) & \to & \text{Blank} \\
    D(1, & b) & \to & D(b+2, 4) \\
    D(2, & b) & \to & D(b+3, 4) \\
-\end{array}</math>let <math>D(a) = D(a, 4)</math>, then we can simplify to:
+\end{array}</math>let <math>D(a):= D(a, 4)</math>, then we can simplify to:
 <math display="block">\begin{array}{lc}
-   D(3k  ) & \to & \textrm{Blank} \\
+   D(3k  ) & \to & \text{Blank} \\
    D(3k+1) & \to & D(5k+6) \\
    D(3k+2) & \to & D(5k+7) \\
@@ Line 20: / Line 22: @@
      & \to & D(7) & \to & D(16) & \to & D(31) & \to & D(56) & \to & D(97) \\
      & \to & D(166) & \to & D(281) & \to & D(472) & \to & D(791) & \to & D(1322) \\
-     & \to & D(2207) & \to & D(3682) & \to & D(6141) & \to & \textrm{Blank} \\
+     & \to & D(2207) & \to & D(3682) & \to & D(6141) & \to & \text{Blank} \\
 \end{array} </math>which has the remarkable luck of applying this [[Collatz-like]] map 14 times before reaching the blanking config (expected # of applications before halting is 3).
@@ Line 27: / Line 29: @@
 == Relation to other machines ==
-The map and trajectory are equivalent to that of the [[BB(5) champion]]. For all <math>k</math>, let <math>f(k)</math> be the number such that <math>D(k)\to D(f(k))</math>, or <math>\text{HALT}</math> if <math>D(k)\to\textrm{Blank}</math>, and let <math>g</math> be the map simulated by the BB(5) champion. Then:
+The map and trajectory are equivalent to that of the [[BB(5) champion]]. For all <math>k</math>, let <math>f(k)</math> be the number such that <math>D(k)\to D(f(k))</math>, or <math>\text{HALT}</math> if <math>D(k)\to\text{Blank}</math>, and let <math>g</math> be the map simulated by the BB(5) champion. Then:
 <math display="block">\begin{array}{lc}
@@ Line 38: / Line 40: @@
 == References ==
+[[Category:BB(4)]]

1RB1LD 1RC1RB 1LC1LA 0RC0RD: Difference between revisions

Latest revision as of 16:54, 3 August 2026

Analysis by Shawn Ligocki

Relation to other machines

References

Navigation menu

Search