https://wiki.bbchallenge.org/w/api.php?action=feedcontributions&feedformat=atom&user=Xl643BusyBeaverWiki - User contributions [en]2026-04-30T20:31:30ZUser contributionsMediaWiki 1.43.5https://wiki.bbchallenge.org/w/index.php?title=User_talk:Xl643&diff=3018User talk:Xl6432025-08-11T06:11:24Z<p>Xl643: </p>
<hr />
<div>== Naming TMs ==<br />
Hi Xl643, please stop adding your own personal names for TMs to their pages. The person who discovers a TM has the right to name it. Or alternatively it might be named if there is a common name used in the community. If you'd like to suggest a name in the talk page or on the Discord you are welcome but don't just add it to the page. [[User:Sligocki|sligocki]] ([[User talk:Sligocki|talk]]) 06:00, 11 August 2025 (UTC)<br />
<br />
That’s fine [[User:Xl643|Xl643]] ([[User talk:Xl643|talk]])</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA&diff=30131RB1RC 1LC1LE 1RA1RD 0RF0RE 1LA0LB ---1RA2025-08-11T05:31:20Z<p>Xl643: </p>
<hr />
<div>{{machine|1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA}}{{unsolved|Does this TM run forever?}}<br />
{{TM|1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA}} is a [[BB(6)]] [[Cryptid]] found by @mxdys and shared on Discord on 27 Jul 2024. It's closely related to [[Hydra]] and [[Antihydra]].<br />
<br />
Xl643 Calls this the '''Ambihydra'''. <br />
== Analysis by @mxdys ==<br />
<pre><br />
antihydra variant:<br />
1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA<br />
<br />
(n,m) := 0^inf C> 01011 01^n 1 01^m 0^inf<br />
<br />
start from (3,1)<br />
(2n+1,m) --> (3n+3,m+2)<br />
(2n,m+1) --> (3n+3,m)<br />
(4n,0) --> (9n+6,1)<br />
(4n+2,0) --> halt<br />
</pre><br />
The rules are proved in [https://github.com/ccz181078/busycoq/blob/BB6/verify/AntiHydra2.v Coq].<br />
<br />
== Analysis by @dyuan01 ==<br />
Using B(a, b) = (3a-6, b), I've come up with these rules:<br />
<pre><br />
Start from B(3, 1)<br />
B(2n, m+1) → B(3n, m)<br />
B(2n+1, m) → B(3n+1, m+2)<br />
B(4n+2, 0) → B(9n+4, 1)<br />
B(4n, 0) → halt<br />
</pre><br />
This is actually just Hydra except you start at B(3, 1) instead of B(3, 0) and you don't necessarily halt if you reach -1. In fact, this can only halt if Hydra halts.<br />
[[Category:Cryptids]]</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=%CE%A3(6,2)&diff=3012Σ(6,2)2025-08-11T05:24:52Z<p>Xl643: Redirected page to BB(6)</p>
<hr />
<div>#Redirect [[BB(6)]]</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=S(6,2)&diff=3011S(6,2)2025-08-11T05:21:20Z<p>Xl643: Redirected page to BB(6)</p>
<hr />
<div>#Redirect [[BB(6)]]</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=%CE%A3(6)&diff=3010Σ(6)2025-08-11T05:20:47Z<p>Xl643: Redirected page to BB(6)</p>
<hr />
<div>#Redirect [[BB(6)]]</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=S(6)&diff=3009S(6)2025-08-11T05:19:51Z<p>Xl643: Redirected page to BB(6)</p>
<hr />
<div>#Redirect [[BB(6)]]</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=User:Xl643&diff=3008User:Xl6432025-08-11T05:17:39Z<p>Xl643: Blanked the page</p>
<hr />
<div></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC&diff=30001RB1LD 1RC1RE 0LA1LB 0LD1LC 1RF0RA ---0RC2025-08-11T01:04:40Z<p>Xl643: </p>
<hr />
<div>{{machine|1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC}}{{unsolved|Does this TM run forever?}}<br />
{{TM|1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC}} is a [[probviously]] non-halting [[BB(6)]] [[Cryptid]] found by @mxdys and shared on Discord on 20 Aug 2024.<br />
<br />
<br />
Xl643 Calls this <nowiki>'''</nowiki>Semi-antihydra<nowiki>'''</nowiki><br />
<br />
== Analysis by @mxdys ==<br />
<pre><br />
1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC<br />
<br />
start: (0,0)<br />
<br />
(3x+0,y) --> (4x+4,y+1)<br />
(3x+1,y+1) --> (4x+5,y+2)<br />
(3x+2,y) --> (4x+8,max(0,y-1))<br />
<br />
(3x+1,0) --> halt<br />
<br />
(x,y) := 0^inf 110 <B 11011 01^x 011^y 0^inf<br />
</pre>After simulating the map for 10^6 steps, x was ~10^124940, while y = 331762. This biased pseudo-random walk did not get lucky and recross the origin early in its trajectory.<br />
[[File:Y t100k 1RB1LD 1RC1RE 0LA1LB 0LD1LC 1RF0RA ---0RC.png|thumb|Plot of y in (x,y) pair described by 1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC. If y = 0 while x is congruent to 1 modulo 3, the TM halts. It is very unlikely that y will ever reach 0 again.]]<br />
[[Category:Cryptids]]</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA&diff=29991RB1RC 1LC1LE 1RA1RD 0RF0RE 1LA0LB ---1RA2025-08-11T01:04:16Z<p>Xl643: </p>
<hr />
<div>{{machine|1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA}}{{unsolved|Does this TM run forever?}}<br />
{{TM|1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA}} is a [[BB(6)]] [[Cryptid]] found by @mxdys and shared on Discord on 27 Jul 2024. It's closely related to [[Hydra]] and [[Antihydra]].<br />
<br />
Xl643 Calls this the '''Ambi-hydra'''<br />
== Analysis by @mxdys ==<br />
<pre><br />
antihydra variant:<br />
1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA<br />
<br />
(n,m) := 0^inf C> 01011 01^n 1 01^m 0^inf<br />
<br />
start from (3,1)<br />
(2n+1,m) --> (3n+3,m+2)<br />
(2n,m+1) --> (3n+3,m)<br />
(4n,0) --> (9n+6,1)<br />
(4n+2,0) --> halt<br />
</pre><br />
The rules are proved in [https://github.com/ccz181078/busycoq/blob/BB6/verify/AntiHydra2.v Coq].<br />
<br />
== Analysis by @dyuan01 ==<br />
Using B(a, b) = (3a-6, b), I've come up with these rules:<br />
<pre><br />
Start from B(3, 1)<br />
B(2n, m+1) → B(3n, m)<br />
B(2n+1, m) → B(3n+1, m+2)<br />
B(4n+2, 0) → B(9n+4, 1)<br />
B(4n, 0) → halt<br />
</pre><br />
This is actually just Hydra except you start at B(3, 1) instead of B(3, 0) and you don't necessarily halt if you reach -1. In fact, this can only halt if Hydra halts.<br />
[[Category:Cryptids]]</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=1RB2LC1RC_2LC---2RB_2LA0LB0RA&diff=29981RB2LC1RC 2LC---2RB 2LA0LB0RA2025-08-11T00:26:50Z<p>Xl643: Maybe this is acceptable.</p>
<hr />
<div>{{machine|1RB2LC1RC_2LC---2RB_2LA0LB0RA}} {{unsolved|Does this TM halt? If so, how many steps does it take to halt?}}<br />
{{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}} is a [[BB(3,3)]] [[holdout]] which appears to [[probviously]] halt. If it can be proven to halt, it will be the BB(3,3) champion in terms of both steps and tape symbols. However, it could also turn out to be a probviously halting [[Cryptid]]. <br />
<br />
This is holdout #758 on Justin's 3x3 mugshots. After about 1.8 million steps and up to some relabelling, it is equivalent to holdout #153: {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}. And if you start in state C it is a [[permutation]] of the same machine. Together, they simulate a complex set of Collatz-like rules with two decreasing parameters. <br />
<br />
After active exploration on the #bb3x3 channel by LegionMammal and dyuan, LegionMammal found (and dyuan confirmed) a configuration A(1,c) (defined [https://discord.com/channels/960643023006490684/1259770474897080380/1259968221218607145 here]) which halts and for which a huge "wall" of previous A(1, c') values all reach it. This gives strong evidence that the TM probviosly halts since jumping over this wall is very "unlikely". <br />
<br />
The user [[User:Xl643|Xl643]] Calls this Turing machine '''Smallfoot'''.<br />
<br />
NOTE: As of 16 Jul 2024 there is a lot more active work on the #bb3x3 channel with LegionMammal and dyuan not reflected here.<br />
<br />
== dyuan01's Rules ==<br />
https://discord.com/channels/960643023006490684/1084047886494470185/1224457633176486041<br />
<br />
<pre><br />
A_1(a, b, c) = 0^inf 1 2^a <C (22)^b (20)^c 0^inf<br />
A_2(a, b, c) = 0^inf 1 2^a <A2 (22)^b (20)^c 0^inf<br />
B(a, b) = 0^inf 1 2^a <B0 (20)^b 0^inf<br />
</pre><br />
<br />
{| class="wikitable"<br />
! From !! To<br />
|-<br />
| A<sub>1</sub>(0, b, 2n) || A<sub>2</sub>(1, b+2n+1, 0)<br />
|-<br />
| A<sub>1</sub>(0, b, 2n+1) || A<sub>1</sub>(1, 0, b+2n+3)<br />
|-<br />
| A<sub>1</sub>(m+1, b, 0) || A<sub>1</sub>(m, 0, b+2)<br />
|-<br />
| A<sub>1</sub>(m+1, b, n+1) || A<sub>2</sub>(m, b+1, n)<br />
|-<br />
| A<sub>2</sub>(0, b, 2n) || A<sub>1</sub>(2b+3, 0, 2n+1)<br />
|-<br />
| A<sub>2</sub>(0, b, 2n+1) || A<sub>2</sub>(2b+3, 2n+1, 0)<br />
|-<br />
| A<sub>2</sub>(m+1, b, 0) || B(m, b+2)<br />
|-<br />
| A<sub>2</sub>(m+1, b, n+1) || A<sub>1</sub>(m, b+2, n)<br />
|-<br />
| B(0, b) || Halt<br />
|-<br />
| B(m+1, 2n) || A<sub>2</sub>(m, 2n+1, 0)<br />
|-<br />
| B(m+1, 2n+1) || A<sub>1</sub>(m, 0, 2n+3)<br />
|}<br />
Starting from A<sub>1</sub>(0, 0, 1) (at step 2).<br />
<br />
== savask's Rules ==<br />
https://discord.com/channels/960643023006490684/1084047886494470185/1254085725138190336<br />
<br />
Let <code>(m, b, n) = A2(m, b, n) = 0^inf 1 2^m <A2 (22)^b (20)^n 0^inf</code><br />
<br />
<pre><br />
(0, b, n) -> (2b+2, 1, n) if n is even<br />
-> (2b, 1, n+3) if n is odd<br />
<br />
(1, b, 0) -> Halt<br />
<br />
(2, b, 0) -> (0, b+3, 0) if b is even<br />
-> (0, 1, b+5) if b is odd<br />
<br />
(m, b, 0) -> (m-2, b+3, 0) if b is even<br />
-> (m-3, 1, b+3) if b is odd<br />
<br />
(1, b, n) -> (0, 1, n+b+2) if n is even<br />
-> Halt if n is odd<br />
<br />
(2, b, 1) -> Halt if b is even<br />
-> (0, 1, b+5) if b is odd<br />
<br />
(m, b, 1) -> (m-3, 1, b+3)<br />
<br />
(m, b, n) -> (m-2, b+3, n-2)<br />
</pre><br />
<br />
https://discord.com/channels/960643023006490684/1084047886494470185/1254306301786198116<br />
<br />
<pre><br />
step (A2 0 b n) | even n = A2 (2*b+2) 1 n<br />
| otherwise = A2 (2*b) 1 (n+3)<br />
-- From now on m > 0<br />
step (A2 1 b 0) = error $ "Halt A2 1 " ++ show b ++ " 0"<br />
step (A2 2 b 0) | even b = A2 0 (b+3) 0<br />
| otherwise = A2 0 1 (b+5)<br />
step (A2 m b 0) | even b = A2 (m-2) (b+3) 0<br />
| otherwise = A2 (m-3) 1 (b+3)<br />
-- From now on n > 0<br />
step (A2 1 b n) | even n = A2 0 1 (n+b+2)<br />
| otherwise = error $ "Halt A2 1 " ++ show b ++ " " ++ show n<br />
step (A2 2 b 1) | even b = error $ "Halt A2 2 " ++ show b ++ " 1"<br />
| otherwise = A2 0 1 (b+5)<br />
step (A2 m b 1) = A2 (m-3) 1 (b+3)<br />
-- Here m > 1, n > 1<br />
step (A2 m b n) = let d2 = (min m n) `div` 2 in A2 (m - 2*d2) (b + 3*d2) (n - 2*d2) -- Accelerated<br />
</pre><br />
<br />
== Shawn's Rules ==<br />
https://discord.com/channels/960643023006490684/1084047886494470185/1254307091863048264<br />
<br />
We can reduce the set of rules from savask's list a bit by noticing that we can evaluate so that all rules end with c even: <br />
<br />
<pre><br />
(0, b, 2c) -> (2b+2, 1, 2c)<br />
<br />
(1, b, 0) -> Halt<br />
(1, 2b, 2c) -> (0, 1, 2(b+c+1))<br />
(1, 2b+1, 2c) -> (2, 1, 2(b+c+3))<br />
<br />
(a, 2b, 0) -> (a-2, 2b+3, 0)<br />
(2, 2b+1, 0) -> (0, 1, 2b+6)<br />
(a, 2b+1, 0) -> (a-3, 1, 2b+4)<br />
<br />
(a, b, c) -> (a-2, b+3, c-2)<br />
</pre><br />
<br />
=== Phases ===<br />
We can think of this going through two different phases. "Even Phase" (where <code>a</code> is even) and "Odd Phase" (where <code>a</code> is odd).<br />
<br />
<pre><br />
Even Phase: a,c even:<br />
(0, b, 2c) -> (2b+2, 1, 2c)<br />
(2a+2, 2b, 0) -> (2a, 2b+3, 0)<br />
(2, 2b+1, 0) -> (0, 1, 2(b+3))<br />
<br />
To Odd Phase:<br />
(2a+4, 2b+1, 0) -> (2a+1, 1, 2b+4)<br />
<br />
Odd Phase: a odd, c even<br />
To Halt:<br />
(1, b, 0) -> Halt<br />
(3, 2b, 0) -> (1, 2b+3, 0) -> Halt<br />
<br />
To Even Phase:<br />
(1, 2b, 2c+2) -> (0, 1, 2(b+c+2))<br />
(1, 2b+1, 2c+2) -> (0, 1, 2b+2c+5) -> (2, 1, 2(b+c+4))<br />
<br />
(2a+5, 2b, 0) -> (2a+3, 2b+3, 0) -> (2a, 1, 2b+6)<br />
(2a+3, 2b+1, 0) -> (2a, 1, 2b+4)<br />
</pre><br />
<br />
So the only way for this to halt is if it is in "Even Phase" and hits (2k+8, 2k+1, 0) or (4k+12, 4k+3, 0) (which will lead to (1, b, 0) or (3, 2b, 0) eventually).<br />
If <code>a</code> is bigger or smaller, then "Odd Phase" will end going back to "Even Phase" again.<br />
<br />
=== Repeated (0, b, 2c) ===<br />
<br />
Let <math>f(n) = 3n+4</math>, then<math display="block">(0, b, 2c) \to (0, f(b), 2(c - b - 1))</math> Let<math display="block">h(n) = f^n(1) + 1 = 3^{n+1} - 1</math><math display="block">g(n) = \sum_{k=0}^{n-1} h(k) = \frac{3}{2} (3^n - 1) - n</math><br />
<br />
<br />
Then if <math>c > g(n)</math>:<math display="block">(0, 1, 2c) \to (0, f^n(1), 2 (c-g(n))) \to (2 h(n), 1, 2 (c-g(n)))</math><br />
<br />
=== Repeated (0, 1, 2c) ===<br />
https://discord.com/channels/960643023006490684/1084047886494470185/1254635277020954705<br />
<br />
Let <math>C(n) = (0, 1, 2n)</math> = <code>0^inf 1 <A2 22 (20)^2n 0^inf</code><br />
<br />
<math display="block">C(g(n) + 8k+1) \to C(g(n) + 8k+1 + n+9)</math><math display="block">\forall k: \frac{h(n) - 45}{65} < k < \frac{h(n) - 22}{38}</math><br />
<br />
Notably, when 8 divides (n+1) then this rule can potentially be applied repeatedly.<br />
<br />
Ex: if n = 7, then we get:<math display="block">\forall k \in [101, 172]: C(3273 + 8k) \to C(3273 + 8(k+2))</math><br />
<br />
<br />
And we see this starting with <math>C(4137) = C(3273 + 8 \cdot 108)</math> which repeats this rule until we get to <math>C(4665) = C(3273 + 8 \cdot 174)</math>.<br />
<br />
And as n gets way bigger, these ranges of repeat will increase exponentially.<br />
<br />
== A(a, c) Rules and Timings ==<br />
<br />
Let A(a, c) = A<sub>1</sub>(a, 0, c) = <code>0^∞ 1 2^a <C (20)^c 0^∞</code>, where A<sub>1</sub>(a, b, c) comes from dyuan01's rules. Then the TM satisfies the following rules once it reaches A(0, 1) after 2 steps. Note that rules (a) and (g) aren't actually reachable from the initial condition.<br />
<br />
{| class="wikitable" style="text-align:left"<br />
|+ Rules and associated step counts ([https://discord.com/channels/960643023006490684/1259770474897080380/1324065684677988505 source])<br />
! !! style="text-align:left" | A(a, c) → !! Conditions !! Step count<br />
|-<br />
! style="text-align:right" | (a)<br />
| A(a−c−1, 3c/2+2) || c ≤ a−1, c ≡ 0 (mod 2) || 3c<sup>2</sup>+8c+5<br />
|-<br />
! style="text-align:right" | (b)<br />
| A(a−c−2, 3(c−1)/2+5) || c ≤ a−2, c ≡ 1 (mod 4) || (6c<sup>2</sup>+31c+37)/2<br />
|-<br />
! style="text-align:right" | (c)<br />
| A(a−c−4, 3(c−1)/2+8) || c ≤ a−4, c ≡ 3 (mod 4) || 3c<sup>2</sup>+29c+65<br />
|-<br />
! style="text-align:right" | (d)<br />
| Halt(3(c−1)/2+7) || c = a−3, c ≡ 3 (mod 4) || (6c<sup>2</sup>+43c+75)/2<br />
|-<br />
! style="text-align:right" | (e)<br />
| A(3c+8, 1) || c = a−2, c ≡ 3 (mod 4) || (6c<sup>2</sup>+37c+63)/2<br />
|-<br />
! style="text-align:right" | (f)<br />
| Halt(3(c−1)/2+4) || c = a−1, c ≡ 1 (mod 2) || 3c<sup>2</sup>+8c+6<br />
|-<br />
! style="text-align:right" | (g)<br />
| Halt(a/2+c+4) || c ≥ a, a ≡ 0, c ≡ 0 (mod 2) || 3a<sup>2</sup>+5a+9c+24<br />
|-<br />
! style="text-align:right" | (h)<br />
| A(1, a/2+c+2) || c ≥ a, a ≡ 0, c ≡ 1 (mod 2) || 3a<sup>2</sup>+3a+5c+11<br />
|-<br />
! style="text-align:right" | (i)<br />
| A(3a, c−a+4) || c ≥ a, a ≡ 1, c ≡ 0 (mod 2) || 3a<sup>2</sup>−9a+14c+30<br />
|-<br />
! style="text-align:right" | (j)<br />
| A(3a+2, c−a+1) || c ≥ a, a ≡ 1, c ≡ 1 (mod 2) || 3a<sup>2</sup>+5c+6<br />
|}<br />
<br />
== Equivalence to 1RB0LB0RC_2LC2LA1RA_1RA1LC--- ==<br />
{{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}, #153, eventually becomes equivalent to this machine. As found by [https://discord.com/channels/960643023006490684/1259770474897080380/1260244842999709726 @Legion], after running the #153 machine for 1,790,901 steps, if one permutes the states A,C, and B and exchanges 1 for 2 and L for R, it has the same configuration as TM #758 after it has run 1,841,608 steps.<br />
<br />
== History ==<br />
LegionMammal's rough timeline of this TM on 30 Apr 2025 ([https://discord.com/channels/960643023006490684/1259770474897080380/1367340727859679322 Discord link]):<br />
<br />
# The machine (and its sibling) pass straight through various rounds of cleverly-written deciders<br />
# dyuan posts his set of rules and looks into it a bit, Justin notes that he'd briefly looked at it some time back<br />
# Shawn and savask write up some acceleration schemes, find empirical evidence that it repeatedly comes close to halting, and speculate that it may actually halt after some period of time<br />
# I take a crack at it myself, this time in terms of chains starting from <code>A(1,c)</code> configs, find some <code>c</code> values leading to a halt (showing that there's no obvious structural barrier), and conjecture some heuristics for how long it should take to reach such a halting <code>c</code> value<br />
# dyuan and I nail down the ideas of 'halter families' (collections of infinitely many halting <code>c</code> values so we don't have to brute-force them) and 'reachability analysis' (obtaining a strong probvious guess of whether a <code>c</code> value will or won't occur in the machine's actual forward behavior, assuming it hasn't halted beforehand)<br />
# dyuan and I race to find a halting <code>c</code> value that 'explodes' (passes the reachability analysis), first within the 'trivial' halter family to no avail, then within all halter families (writing a program to enumerate halter families is extremely fiddly, at this point I treat some of my own code as a black box not to be touched)<br />
# By dint of a somewhat more performant program, I find (and dyuan confirms) the <math>c = \frac{3^{307}-8\,282\,708\,212}{13\,959\,275}</math> we all know and love, probviously sealing the machine's fate<br />
[[Category:Cryptids]]</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=1RB2LC1RC_2LC---2RB_2LA0LB0RA&diff=28831RB2LC1RC 2LC---2RB 2LA0LB0RA2025-08-10T00:06:18Z<p>Xl643: </p>
<hr />
<div>{{machine|1RB2LC1RC_2LC---2RB_2LA0LB0RA}} aka Smallfoot {{unsolved|Does this TM halt? If so, how many steps does it take to halt?}}<br />
{{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}}<br />
<br />
This is a [[BB(3,3)]] [[holdout]] which appears to [[probviously]] halt. If can be proven to halt, it will be the BB(3,3) champion, in terms of both steps and tape symbols. However, it could also turn out to be a probviously halting [[Cryptid]]. <br />
<br />
This is holdout #758 on Justin's 3x3 mugshots. After about 1.8 million steps and up to some relabelling, it is equivalent to holdout #153: {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}. And if you start in state C it is a [[permutation]] of the same machine. Together, they simulate a complex set of Collatz-like rules with two decreasing parameters. <br />
<br />
After active exploration on the #bb3x3 channel by LegionMammal and dyuan, LegionMammal found (and dyuan confirmed) a configuration A(1,c) (defined [https://discord.com/channels/960643023006490684/1259770474897080380/1259968221218607145 here]) which halts and for which a huge "wall" of previous A(1, c') values all reach it. This gives strong evidence that the TM probviosly halts since jumping over this wall is very "unlikely". <br />
<br />
NOTE: As of 16 Jul 2024 there is a lot more active work on the #bb3x3 channel with LegionMammal and dyuan not reflected here.<br />
<br />
== dyuan01's Rules ==<br />
https://discord.com/channels/960643023006490684/1084047886494470185/1224457633176486041<br />
<br />
<pre><br />
A_1(a, b, c) = 0^inf 1 2^a <C (22)^b (20)^c 0^inf<br />
A_2(a, b, c) = 0^inf 1 2^a <A2 (22)^b (20)^c 0^inf<br />
B(a, b) = 0^inf 1 2^a <B0 (20)^b 0^inf<br />
</pre><br />
<br />
{| class="wikitable"<br />
! From !! To<br />
|-<br />
| A<sub>1</sub>(0, b, 2n) || A<sub>2</sub>(1, b+2n+1, 0)<br />
|-<br />
| A<sub>1</sub>(0, b, 2n+1) || A<sub>1</sub>(1, 0, b+2n+3)<br />
|-<br />
| A<sub>1</sub>(m+1, b, 0) || A<sub>1</sub>(m, 0, b+2)<br />
|-<br />
| A<sub>1</sub>(m+1, b, n+1) || A<sub>2</sub>(m, b+1, n)<br />
|-<br />
| A<sub>2</sub>(0, b, 2n) || A<sub>1</sub>(2b+3, 0, 2n+1)<br />
|-<br />
| A<sub>2</sub>(0, b, 2n+1) || A<sub>2</sub>(2b+3, 2n+1, 0)<br />
|-<br />
| A<sub>2</sub>(m+1, b, 0) || B(m, b+2)<br />
|-<br />
| A<sub>2</sub>(m+1, b, n+1) || A<sub>1</sub>(m, b+2, n)<br />
|-<br />
| B(0, b) || Halt<br />
|-<br />
| B(m+1, 2n) || A<sub>2</sub>(m, 2n+1, 0)<br />
|-<br />
| B(m+1, 2n+1) || A<sub>1</sub>(m, 0, 2n+3)<br />
|}<br />
Starting from A<sub>1</sub>(0, 0, 1) (at step 2).<br />
<br />
== savask's Rules ==<br />
https://discord.com/channels/960643023006490684/1084047886494470185/1254085725138190336<br />
<br />
Let <code>(m, b, n) = A2(m, b, n) = 0^inf 1 2^m <A2 (22)^b (20)^n 0^inf</code><br />
<br />
<pre><br />
(0, b, n) -> (2b+2, 1, n) if n is even<br />
-> (2b, 1, n+3) if n is odd<br />
<br />
(1, b, 0) -> Halt<br />
<br />
(2, b, 0) -> (0, b+3, 0) if b is even<br />
-> (0, 1, b+5) if b is odd<br />
<br />
(m, b, 0) -> (m-2, b+3, 0) if b is even<br />
-> (m-3, 1, b+3) if b is odd<br />
<br />
(1, b, n) -> (0, 1, n+b+2) if n is even<br />
-> Halt if n is odd<br />
<br />
(2, b, 1) -> Halt if b is even<br />
-> (0, 1, b+5) if b is odd<br />
<br />
(m, b, 1) -> (m-3, 1, b+3)<br />
<br />
(m, b, n) -> (m-2, b+3, n-2)<br />
</pre><br />
<br />
https://discord.com/channels/960643023006490684/1084047886494470185/1254306301786198116<br />
<br />
<pre><br />
step (A2 0 b n) | even n = A2 (2*b+2) 1 n<br />
| otherwise = A2 (2*b) 1 (n+3)<br />
-- From now on m > 0<br />
step (A2 1 b 0) = error $ "Halt A2 1 " ++ show b ++ " 0"<br />
step (A2 2 b 0) | even b = A2 0 (b+3) 0<br />
| otherwise = A2 0 1 (b+5)<br />
step (A2 m b 0) | even b = A2 (m-2) (b+3) 0<br />
| otherwise = A2 (m-3) 1 (b+3)<br />
-- From now on n > 0<br />
step (A2 1 b n) | even n = A2 0 1 (n+b+2)<br />
| otherwise = error $ "Halt A2 1 " ++ show b ++ " " ++ show n<br />
step (A2 2 b 1) | even b = error $ "Halt A2 2 " ++ show b ++ " 1"<br />
| otherwise = A2 0 1 (b+5)<br />
step (A2 m b 1) = A2 (m-3) 1 (b+3)<br />
-- Here m > 1, n > 1<br />
step (A2 m b n) = let d2 = (min m n) `div` 2 in A2 (m - 2*d2) (b + 3*d2) (n - 2*d2) -- Accelerated<br />
</pre><br />
<br />
== Shawn's Rules ==<br />
https://discord.com/channels/960643023006490684/1084047886494470185/1254307091863048264<br />
<br />
We can reduce the set of rules from savask's list a bit by noticing that we can evaluate so that all rules end with c even: <br />
<br />
<pre><br />
(0, b, 2c) -> (2b+2, 1, 2c)<br />
<br />
(1, b, 0) -> Halt<br />
(1, 2b, 2c) -> (0, 1, 2(b+c+1))<br />
(1, 2b+1, 2c) -> (2, 1, 2(b+c+3))<br />
<br />
(a, 2b, 0) -> (a-2, 2b+3, 0)<br />
(2, 2b+1, 0) -> (0, 1, 2b+6)<br />
(a, 2b+1, 0) -> (a-3, 1, 2b+4)<br />
<br />
(a, b, c) -> (a-2, b+3, c-2)<br />
</pre><br />
<br />
=== Phases ===<br />
We can think of this going through two different phases. "Even Phase" (where <code>a</code> is even) and "Odd Phase" (where <code>a</code> is odd).<br />
<br />
<pre><br />
Even Phase: a,c even:<br />
(0, b, 2c) -> (2b+2, 1, 2c)<br />
(2a+2, 2b, 0) -> (2a, 2b+3, 0)<br />
(2, 2b+1, 0) -> (0, 1, 2(b+3))<br />
<br />
To Odd Phase:<br />
(2a+4, 2b+1, 0) -> (2a+1, 1, 2b+4)<br />
<br />
Odd Phase: a odd, c even<br />
To Halt:<br />
(1, b, 0) -> Halt<br />
(3, 2b, 0) -> (1, 2b+3, 0) -> Halt<br />
<br />
To Even Phase:<br />
(1, 2b, 2c+2) -> (0, 1, 2(b+c+2))<br />
(1, 2b+1, 2c+2) -> (0, 1, 2b+2c+5) -> (2, 1, 2(b+c+4))<br />
<br />
(2a+5, 2b, 0) -> (2a+3, 2b+3, 0) -> (2a, 1, 2b+6)<br />
(2a+3, 2b+1, 0) -> (2a, 1, 2b+4)<br />
</pre><br />
<br />
So the only way for this to halt is if it is in "Even Phase" and hits (2k+8, 2k+1, 0) or (4k+12, 4k+3, 0) (which will lead to (1, b, 0) or (3, 2b, 0) eventually).<br />
If <code>a</code> is bigger or smaller, then "Odd Phase" will end going back to "Even Phase" again.<br />
<br />
=== Repeated (0, b, 2c) ===<br />
<br />
Let <math>f(n) = 3n+4</math>, then<math display="block">(0, b, 2c) \to (0, f(b), 2(c - b - 1))</math> Let<math display="block">h(n) = f^n(1) + 1 = 3^{n+1} - 1</math><math display="block">g(n) = \sum_{k=0}^{n-1} h(k) = \frac{3}{2} (3^n - 1) - n</math><br />
<br />
<br />
Then if <math>c > g(n)</math>:<math display="block">(0, 1, 2c) \to (0, f^n(1), 2 (c-g(n))) \to (2 h(n), 1, 2 (c-g(n)))</math><br />
<br />
=== Repeated (0, 1, 2c) ===<br />
https://discord.com/channels/960643023006490684/1084047886494470185/1254635277020954705<br />
<br />
Let <math>C(n) = (0, 1, 2n)</math> = <code>0^inf 1 <A2 22 (20)^2n 0^inf</code><br />
<br />
<math display="block">C(g(n) + 8k+1) \to C(g(n) + 8k+1 + n+9)</math><math display="block">\forall k: \frac{h(n) - 45}{65} < k < \frac{h(n) - 22}{38}</math><br />
<br />
Notably, when 8 divides (n+1) then this rule can potentially be applied repeatedly.<br />
<br />
Ex: if n = 7, then we get:<math display="block">\forall k \in [101, 172]: C(3273 + 8k) \to C(3273 + 8(k+2))</math><br />
<br />
<br />
And we see this starting with <math>C(4137) = C(3273 + 8 \cdot 108)</math> which repeats this rule until we get to <math>C(4665) = C(3273 + 8 \cdot 174)</math>.<br />
<br />
And as n gets way bigger, these ranges of repeat will increase exponentially.<br />
<br />
== A(a, c) Rules and Timings ==<br />
<br />
Let A(a, c) = A<sub>1</sub>(a, 0, c) = <code>0^∞ 1 2^a <C (20)^c 0^∞</code>, where A<sub>1</sub>(a, b, c) comes from dyuan01's rules. Then the TM satisfies the following rules once it reaches A(0, 1) after 2 steps. Note that rules (a) and (g) aren't actually reachable from the initial condition.<br />
<br />
{| class="wikitable" style="text-align:left"<br />
|+ Rules and associated step counts ([https://discord.com/channels/960643023006490684/1259770474897080380/1324065684677988505 source])<br />
! !! style="text-align:left" | A(a, c) → !! Conditions !! Step count<br />
|-<br />
! style="text-align:right" | (a)<br />
| A(a−c−1, 3c/2+2) || c ≤ a−1, c ≡ 0 (mod 2) || 3c<sup>2</sup>+8c+5<br />
|-<br />
! style="text-align:right" | (b)<br />
| A(a−c−2, 3(c−1)/2+5) || c ≤ a−2, c ≡ 1 (mod 4) || (6c<sup>2</sup>+31c+37)/2<br />
|-<br />
! style="text-align:right" | (c)<br />
| A(a−c−4, 3(c−1)/2+8) || c ≤ a−4, c ≡ 3 (mod 4) || 3c<sup>2</sup>+29c+65<br />
|-<br />
! style="text-align:right" | (d)<br />
| Halt(3(c−1)/2+7) || c = a−3, c ≡ 3 (mod 4) || (6c<sup>2</sup>+43c+75)/2<br />
|-<br />
! style="text-align:right" | (e)<br />
| A(3c+8, 1) || c = a−2, c ≡ 3 (mod 4) || (6c<sup>2</sup>+37c+63)/2<br />
|-<br />
! style="text-align:right" | (f)<br />
| Halt(3(c−1)/2+4) || c = a−1, c ≡ 1 (mod 2) || 3c<sup>2</sup>+8c+6<br />
|-<br />
! style="text-align:right" | (g)<br />
| Halt(a/2+c+4) || c ≥ a, a ≡ 0, c ≡ 0 (mod 2) || 3a<sup>2</sup>+5a+9c+24<br />
|-<br />
! style="text-align:right" | (h)<br />
| A(1, a/2+c+2) || c ≥ a, a ≡ 0, c ≡ 1 (mod 2) || 3a<sup>2</sup>+3a+5c+11<br />
|-<br />
! style="text-align:right" | (i)<br />
| A(3a, c−a+4) || c ≥ a, a ≡ 1, c ≡ 0 (mod 2) || 3a<sup>2</sup>−9a+14c+30<br />
|-<br />
! style="text-align:right" | (j)<br />
| A(3a+2, c−a+1) || c ≥ a, a ≡ 1, c ≡ 1 (mod 2) || 3a<sup>2</sup>+5c+6<br />
|}<br />
<br />
== Equivalence to 1RB0LB0RC_2LC2LA1RA_1RA1LC--- ==<br />
{{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}, #153, eventually becomes equivalent to this machine. As found by [https://discord.com/channels/960643023006490684/1259770474897080380/1260244842999709726 @Legion], after running the #153 machine for 1,790,901 steps, if one permutes the states A,C, and B and exchanges 1 for 2 and L for R, it has the same configuration as TM #758 after it has run 1,841,608 steps.<br />
<br />
== History ==<br />
LegionMammal's rough timeline of this TM on 30 Apr 2025 ([https://discord.com/channels/960643023006490684/1259770474897080380/1367340727859679322 Discord link]):<br />
<br />
# The machine (and its sibling) pass straight through various rounds of cleverly-written deciders<br />
# dyuan posts his set of rules and looks into it a bit, Justin notes that he'd briefly looked at it some time back<br />
# Shawn and savask write up some acceleration schemes, find empirical evidence that it repeatedly comes close to halting, and speculate that it may actually halt after some period of time<br />
# I take a crack at it myself, this time in terms of chains starting from <code>A(1,c)</code> configs, find some <code>c</code> values leading to a halt (showing that there's no obvious structural barrier), and conjecture some heuristics for how long it should take to reach such a halting <code>c</code> value<br />
# dyuan and I nail down the ideas of 'halter families' (collections of infinitely many halting <code>c</code> values so we don't have to brute-force them) and 'reachability analysis' (obtaining a strong probvious guess of whether a <code>c</code> value will or won't occur in the machine's actual forward behavior, assuming it hasn't halted beforehand)<br />
# dyuan and I race to find a halting <code>c</code> value that 'explodes' (passes the reachability analysis), first within the 'trivial' halter family to no avail, then within all halter families (writing a program to enumerate halter families is extremely fiddly, at this point I treat some of my own code as a black box not to be touched)<br />
# By dint of a somewhat more performant program, I find (and dyuan confirms) the <math>c = \frac{3^{307}-8\,282\,708\,212}{13\,959\,275}</math> we all know and love, probviously sealing the machine's fate<br />
[[Category:Cryptids]]</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Main_Page&diff=2291Main Page2025-06-27T20:11:08Z<p>Xl643: </p>
<hr />
<div>The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 for 2-symbol [[Turing machines]] and later generalised to ''m''-symbol Turing machines:<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref><ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref><br />
<br />
{| class="wikitable"<br />
|-<br />
| BB(''n'', ''m'') = Maximum number of steps taken by a halting ''n''-state, ''m''-symbol Turing machine starting from a blank (all 0) tape<br />
|}<br />
<br />
The 2-symbol case BB(''n'', 2) is abbreviated as BB(''n''). The busy beaver function is not computable, but a few of its values are known:<br />
<br />
{| class="wikitable"<br />
|+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref><br />
! !!2-state!!3-state !!4-state!!5-state!!6-state <br />
!7-state<br />
|- <br />
! 2-symbol <br />
| [[BB(2)]] = 4 <br />
| [[BB(3)]] = 6<br />
| [[BB(4)]] = 13 <br />
| [[BB(5)]] = 4,098<br />
| style="background: orange;" | [[BB(6)]] > <math>2 \uparrow \uparrow \uparrow 5</math><br />
| style="background: #ffe4b2;" | [[BB(7)]] > <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> <br />
|-<br />
! 3-symbol<br />
| [[BB(2,3)]] = 9 <br />
| style="background: orange;" | [[BB(3,3)]] > <math>10^{8}</math><br />
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>2 \uparrow\uparrow\uparrow 2^{2^{32}}</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 4-symbol <br />
| [[BB(2,4)]] = 2,050 <br />
| style="background: #ffe4b2;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 5-symbol <br />
| style="background: orange;" | [[BB(2,5)]] > <math>10\uparrow\uparrow 4</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 6-symbol <br />
| style="background: #ffe4b2;" | [[BB(2,6)]] > <math>10 \uparrow\uparrow\uparrow 3</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|}<br />
<br />
In the above table, <span style="background: orange">cells are highlighted in orange</span> when there are known [[Cryptids]] (mathematically-hard machines) in that class, and <span style="background: #ffe4b2">cells are highlighted in light orange</span> when the existence of a Cryptid is given by using a known one with less states or symbols.<br />
<br />
== About bbchallenge ==<br />
[https://www.bbchallenge.org bbchallenge] is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:<br />
<br />
* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Coq_(software) Coq])<br />
* Maintaining [[Holdouts lists]] for small busy beaver values<br />
* Proving the behavior of [[:Category:Individual Machines|Individual machines]]<br />
* Finding [[Cryptids]] (mathematically-hard machines)<br />
* Searching for new [[Champions]]<br />
* Building [[Accelerated Simulator]]s to simulate halting machines faster<br />
* Writing papers and giving talks about busy beaver, see [[Papers & Talks]]<br />
<br />
In June 2024, bbchallenge achieved a significant milestone by proving in Coq / Rocq that the 5th busy beaver value, [[BB(5)]], is equal to the lower bound found in 1989: 47,176,870.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.<br />
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref><br />
<br />
== Contribute to this wiki ==<br />
This wiki is collaborative, feel free to contribute by editing existing pages or creating new ones:<br />
<br />
<inputbox><br />
type=create<br />
width=100<br />
break=no<br />
buttonlabel=Create new article<br />
default=(Article title)<br />
</inputbox><br />
<br />
==Notes==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Main_Page&diff=2290Main Page2025-06-27T20:10:12Z<p>Xl643: </p>
<hr />
<div>The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 for 2-symbol [[Turing machines]] and later generalised to ''m''-symbol Turing machines:<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref><ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref><br />
<br />
{| class="wikitable"<br />
|-<br />
| BB(''n'', ''m'') = Maximum number of steps taken by a halting ''n''-state, ''m''-symbol Turing machine starting from a blank (all 0) tape<br />
|}<br />
<br />
The 2-symbol case BB(''n'', 2) is abbreviated as BB(''n''). The busy beaver function is not computable, but a few of its values are known:<br />
<br />
{| class="wikitable"<br />
|+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref><br />
! !!2-state!!3-state !!4-state!!5-state!!6-state <br />
!7-state<br />
|- <br />
! 2-symbol <br />
| [[BB(2)]] = 4 <br />
| [[BB(3)]] = 6<br />
| [[BB(4)]] = 13 <br />
| [[BB(5)]] = 4,098<br />
| style="background: orange;" | [[BB(6)]] > <math>2 \uparrow \uparrow \uparrow 5</math><br />
| style="background: #ffe4b2;" | [[BB(7)]] > <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> <br />
|-<br />
! 3-symbol<br />
| [[BB(2,3)]] = 38 <br />
| style="background: orange;" | [[BB(3,3)]] > <math>10^{8}</math><br />
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>2 \uparrow\uparrow\uparrow 2^{2^{32}}</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 4-symbol <br />
| [[BB(2,4)]] = 2,050 <br />
| style="background: #ffe4b2;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 5-symbol <br />
| style="background: orange;" | [[BB(2,5)]] > <math>10\uparrow\uparrow 4</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 6-symbol <br />
| style="background: #ffe4b2;" | [[BB(2,6)]] > <math>10 \uparrow\uparrow\uparrow 3</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|}<br />
<br />
In the above table, <span style="background: orange">cells are highlighted in orange</span> when there are known [[Cryptids]] (mathematically-hard machines) in that class, and <span style="background: #ffe4b2">cells are highlighted in light orange</span> when the existence of a Cryptid is given by using a known one with less states or symbols.<br />
<br />
== About bbchallenge ==<br />
[https://www.bbchallenge.org bbchallenge] is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:<br />
<br />
* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Coq_(software) Coq])<br />
* Maintaining [[Holdouts lists]] for small busy beaver values<br />
* Proving the behavior of [[:Category:Individual Machines|Individual machines]]<br />
* Finding [[Cryptids]] (mathematically-hard machines)<br />
* Searching for new [[Champions]]<br />
* Building [[Accelerated Simulator]]s to simulate halting machines faster<br />
* Writing papers and giving talks about busy beaver, see [[Papers & Talks]]<br />
<br />
In June 2024, bbchallenge achieved a significant milestone by proving in Coq / Rocq that the 5th busy beaver value, [[BB(5)]], is equal to the lower bound found in 1989: 47,176,870.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.<br />
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref><br />
<br />
== Contribute to this wiki ==<br />
This wiki is collaborative, feel free to contribute by editing existing pages or creating new ones:<br />
<br />
<inputbox><br />
type=create<br />
width=100<br />
break=no<br />
buttonlabel=Create new article<br />
default=(Article title)<br />
</inputbox><br />
<br />
==Notes==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Main_Page&diff=2289Main Page2025-06-27T20:07:59Z<p>Xl643: </p>
<hr />
<div>The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 for 2-symbol [[Turing machines]] and later generalised to ''m''-symbol Turing machines:<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref><ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref><br />
<br />
{| class="wikitable"<br />
|-<br />
| BB(''n'', ''m'') = Maximum number of steps taken by a halting ''n''-state, ''m''-symbol Turing machine starting from a blank (all 0) tape<br />
|}<br />
<br />
The 2-symbol case BB(''n'', 2) is abbreviated as BB(''n''). The busy beaver function is not computable, but a few of its values are known:<br />
<br />
{| class="wikitable"<br />
|+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref><br />
! !!2-state!!3-state !!4-state!!5-state!!6-state <br />
!7-state<br />
|- <br />
! 2-symbol <br />
| [[BB(2)]] = 4 <br />
| [[BB(3)]] = 6<br />
| [[BB(4)]] = 13 <br />
| [[BB(5)]] = 4,098<br />
| style="background: orange;" | [[BB(6)]] > <math>2 \uparrow \uparrow \uparrow 5</math><br />
| style="background: #ffe4b2;" | [[BB(7)]] > <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> <br />
|-<br />
! 3-symbol<br />
| [[BB(2,3)]] = 38 <br />
| style="background: orange;" | [[BB(3,3)]] > <math>10^{8}</math><br />
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>2 \uparrow\uparrow\uparrow 2^{2^{32}}</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 4-symbol <br />
| [[BB(2,4)]] = 3,932,964<br />
| style="background: #ffe4b2;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 5-symbol <br />
| style="background: orange;" | [[BB(2,5)]] > <math>10\uparrow\uparrow 4</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 6-symbol <br />
| style="background: #ffe4b2;" | [[BB(2,6)]] > <math>10 \uparrow\uparrow\uparrow 3</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|}<br />
<br />
In the above table, <span style="background: orange">cells are highlighted in orange</span> when there are known [[Cryptids]] (mathematically-hard machines) in that class, and <span style="background: #ffe4b2">cells are highlighted in light orange</span> when the existence of a Cryptid is given by using a known one with less states or symbols.<br />
<br />
== About bbchallenge ==<br />
[https://www.bbchallenge.org bbchallenge] is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:<br />
<br />
* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Coq_(software) Coq])<br />
* Maintaining [[Holdouts lists]] for small busy beaver values<br />
* Proving the behavior of [[:Category:Individual Machines|Individual machines]]<br />
* Finding [[Cryptids]] (mathematically-hard machines)<br />
* Searching for new [[Champions]]<br />
* Building [[Accelerated Simulator]]s to simulate halting machines faster<br />
* Writing papers and giving talks about busy beaver, see [[Papers & Talks]]<br />
<br />
In June 2024, bbchallenge achieved a significant milestone by proving in Coq / Rocq that the 5th busy beaver value, [[BB(5)]], is equal to the lower bound found in 1989: 47,176,870.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.<br />
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref><br />
<br />
== Contribute to this wiki ==<br />
This wiki is collaborative, feel free to contribute by editing existing pages or creating new ones:<br />
<br />
<inputbox><br />
type=create<br />
width=100<br />
break=no<br />
buttonlabel=Create new article<br />
default=(Article title)<br />
</inputbox><br />
<br />
==Notes==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Main_Page&diff=2288Main Page2025-06-27T20:07:12Z<p>Xl643: </p>
<hr />
<div>The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 for 2-symbol [[Turing machines]] and later generalised to ''m''-symbol Turing machines:<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref><ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref><br />
<br />
{| class="wikitable"<br />
|-<br />
| BB(''n'', ''m'') = Maximum number of steps taken by a halting ''n''-state, ''m''-symbol Turing machine starting from a blank (all 0) tape<br />
|}<br />
<br />
The 2-symbol case BB(''n'', 2) is abbreviated as BB(''n''). The busy beaver function is not computable, but a few of its values are known:<br />
<br />
{| class="wikitable"<br />
|+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref><br />
! !!2-state!!3-state !!4-state!!5-state!!6-state <br />
!7-state<br />
|- <br />
! 2-symbol <br />
| [[BB(2)]] = 4 <br />
| [[BB(3)]] = 6<br />
| [[BB(4)]] = 107 <br />
| [[BB(5)]] = 4,098<br />
| style="background: orange;" | [[BB(6)]] > <math>2 \uparrow \uparrow \uparrow 5</math><br />
| style="background: #ffe4b2;" | [[BB(7)]] > <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> <br />
|-<br />
! 3-symbol<br />
| [[BB(2,3)]] = 38 <br />
| style="background: orange;" | [[BB(3,3)]] > <math>10^{8}</math><br />
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>2 \uparrow\uparrow\uparrow 2^{2^{32}}</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 4-symbol <br />
| [[BB(2,4)]] = 3,932,964<br />
| style="background: #ffe4b2;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 5-symbol <br />
| style="background: orange;" | [[BB(2,5)]] > <math>10\uparrow\uparrow 4</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 6-symbol <br />
| style="background: #ffe4b2;" | [[BB(2,6)]] > <math>10 \uparrow\uparrow\uparrow 3</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|}<br />
<br />
In the above table, <span style="background: orange">cells are highlighted in orange</span> when there are known [[Cryptids]] (mathematically-hard machines) in that class, and <span style="background: #ffe4b2">cells are highlighted in light orange</span> when the existence of a Cryptid is given by using a known one with less states or symbols.<br />
<br />
== About bbchallenge ==<br />
[https://www.bbchallenge.org bbchallenge] is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:<br />
<br />
* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Coq_(software) Coq])<br />
* Maintaining [[Holdouts lists]] for small busy beaver values<br />
* Proving the behavior of [[:Category:Individual Machines|Individual machines]]<br />
* Finding [[Cryptids]] (mathematically-hard machines)<br />
* Searching for new [[Champions]]<br />
* Building [[Accelerated Simulator]]s to simulate halting machines faster<br />
* Writing papers and giving talks about busy beaver, see [[Papers & Talks]]<br />
<br />
In June 2024, bbchallenge achieved a significant milestone by proving in Coq / Rocq that the 5th busy beaver value, [[BB(5)]], is equal to the lower bound found in 1989: 47,176,870.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.<br />
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref><br />
<br />
== Contribute to this wiki ==<br />
This wiki is collaborative, feel free to contribute by editing existing pages or creating new ones:<br />
<br />
<inputbox><br />
type=create<br />
width=100<br />
break=no<br />
buttonlabel=Create new article<br />
default=(Article title)<br />
</inputbox><br />
<br />
==Notes==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Main_Page&diff=2287Main Page2025-06-27T20:06:54Z<p>Xl643: </p>
<hr />
<div>The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 for 2-symbol [[Turing machines]] and later generalised to ''m''-symbol Turing machines:<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref><ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref><br />
<br />
{| class="wikitable"<br />
|-<br />
| BB(''n'', ''m'') = Maximum number of steps taken by a halting ''n''-state, ''m''-symbol Turing machine starting from a blank (all 0) tape<br />
|}<br />
<br />
The 2-symbol case BB(''n'', 2) is abbreviated as BB(''n''). The busy beaver function is not computable, but a few of its values are known:<br />
<br />
{| class="wikitable"<br />
|+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref><br />
! !!2-state!!3-state !!4-state!!5-state!!6-state <br />
!7-state<br />
|- <br />
! 2-symbol <br />
| [[BB(2)]] = 6 <br />
| [[BB(3)]] = 6<br />
| [[BB(4)]] = 107 <br />
| [[BB(5)]] = 4,098<br />
| style="background: orange;" | [[BB(6)]] > <math>2 \uparrow \uparrow \uparrow 5</math><br />
| style="background: #ffe4b2;" | [[BB(7)]] > <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> <br />
|-<br />
! 3-symbol<br />
| [[BB(2,3)]] = 38 <br />
| style="background: orange;" | [[BB(3,3)]] > <math>10^{8}</math><br />
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>2 \uparrow\uparrow\uparrow 2^{2^{32}}</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 4-symbol <br />
| [[BB(2,4)]] = 3,932,964<br />
| style="background: #ffe4b2;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 5-symbol <br />
| style="background: orange;" | [[BB(2,5)]] > <math>10\uparrow\uparrow 4</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 6-symbol <br />
| style="background: #ffe4b2;" | [[BB(2,6)]] > <math>10 \uparrow\uparrow\uparrow 3</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|}<br />
<br />
In the above table, <span style="background: orange">cells are highlighted in orange</span> when there are known [[Cryptids]] (mathematically-hard machines) in that class, and <span style="background: #ffe4b2">cells are highlighted in light orange</span> when the existence of a Cryptid is given by using a known one with less states or symbols.<br />
<br />
== About bbchallenge ==<br />
[https://www.bbchallenge.org bbchallenge] is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:<br />
<br />
* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Coq_(software) Coq])<br />
* Maintaining [[Holdouts lists]] for small busy beaver values<br />
* Proving the behavior of [[:Category:Individual Machines|Individual machines]]<br />
* Finding [[Cryptids]] (mathematically-hard machines)<br />
* Searching for new [[Champions]]<br />
* Building [[Accelerated Simulator]]s to simulate halting machines faster<br />
* Writing papers and giving talks about busy beaver, see [[Papers & Talks]]<br />
<br />
In June 2024, bbchallenge achieved a significant milestone by proving in Coq / Rocq that the 5th busy beaver value, [[BB(5)]], is equal to the lower bound found in 1989: 47,176,870.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.<br />
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref><br />
<br />
== Contribute to this wiki ==<br />
This wiki is collaborative, feel free to contribute by editing existing pages or creating new ones:<br />
<br />
<inputbox><br />
type=create<br />
width=100<br />
break=no<br />
buttonlabel=Create new article<br />
default=(Article title)<br />
</inputbox><br />
<br />
==Notes==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Main_Page&diff=2286Main Page2025-06-27T20:05:38Z<p>Xl643: </p>
<hr />
<div>The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 for 2-symbol [[Turing machines]] and later generalised to ''m''-symbol Turing machines:<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref><ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref><br />
<br />
{| class="wikitable"<br />
|-<br />
| BB(''n'', ''m'') = Maximum number of steps taken by a halting ''n''-state, ''m''-symbol Turing machine starting from a blank (all 0) tape<br />
|}<br />
<br />
The 2-symbol case BB(''n'', 2) is abbreviated as BB(''n''). The busy beaver function is not computable, but a few of its values are known:<br />
<br />
{| class="wikitable"<br />
|+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref><br />
! !!2-state!!3-state !!4-state!!5-state!!6-state <br />
!7-state<br />
|- <br />
! 2-symbol <br />
| [[BB(2)]] = 6 <br />
| [[BB(3)]] = 21<br />
| [[BB(4)]] = 107 <br />
| [[BB(5)]] = 4,098<br />
| style="background: orange;" | [[BB(6)]] > <math>2 \uparrow \uparrow \uparrow 5</math><br />
| style="background: #ffe4b2;" | [[BB(7)]] > <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> <br />
|-<br />
! 3-symbol<br />
| [[BB(2,3)]] = 38 <br />
| style="background: orange;" | [[BB(3,3)]] > <math>10^{8}</math><br />
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>2 \uparrow\uparrow\uparrow 2^{2^{32}}</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 4-symbol <br />
| [[BB(2,4)]] = 3,932,964<br />
| style="background: #ffe4b2;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 5-symbol <br />
| style="background: orange;" | [[BB(2,5)]] > <math>10\uparrow\uparrow 4</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 6-symbol <br />
| style="background: #ffe4b2;" | [[BB(2,6)]] > <math>10 \uparrow\uparrow\uparrow 3</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|}<br />
<br />
In the above table, <span style="background: orange">cells are highlighted in orange</span> when there are known [[Cryptids]] (mathematically-hard machines) in that class, and <span style="background: #ffe4b2">cells are highlighted in light orange</span> when the existence of a Cryptid is given by using a known one with less states or symbols.<br />
<br />
== About bbchallenge ==<br />
[https://www.bbchallenge.org bbchallenge] is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:<br />
<br />
* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Coq_(software) Coq])<br />
* Maintaining [[Holdouts lists]] for small busy beaver values<br />
* Proving the behavior of [[:Category:Individual Machines|Individual machines]]<br />
* Finding [[Cryptids]] (mathematically-hard machines)<br />
* Searching for new [[Champions]]<br />
* Building [[Accelerated Simulator]]s to simulate halting machines faster<br />
* Writing papers and giving talks about busy beaver, see [[Papers & Talks]]<br />
<br />
In June 2024, bbchallenge achieved a significant milestone by proving in Coq / Rocq that the 5th busy beaver value, [[BB(5)]], is equal to the lower bound found in 1989: 47,176,870.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.<br />
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref><br />
<br />
== Contribute to this wiki ==<br />
This wiki is collaborative, feel free to contribute by editing existing pages or creating new ones:<br />
<br />
<inputbox><br />
type=create<br />
width=100<br />
break=no<br />
buttonlabel=Create new article<br />
default=(Article title)<br />
</inputbox><br />
<br />
==Notes==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Main_Page&diff=2285Main Page2025-06-27T20:04:42Z<p>Xl643: </p>
<hr />
<div>The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [https://en.wikipedia.org/wiki/Tibor_Rad%C3%B3 Tibor Radó] in 1962 for 2-symbol [[Turing machines]] and later generalised to ''m''-symbol Turing machines:<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref><ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref><br />
<br />
{| class="wikitable"<br />
|-<br />
| BB(''n'', ''m'') = Maximum number of steps taken by a halting ''n''-state, ''m''-symbol Turing machine starting from a blank (all 0) tape<br />
|}<br />
<br />
The 2-symbol case BB(''n'', 2) is abbreviated as BB(''n''). The busy beaver function is not computable, but a few of its values are known:<br />
<br />
{| class="wikitable"<br />
|+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref><br />
! !!2-state!!3-state !!4-state!!5-state!!6-state <br />
!7-state<br />
|- <br />
! 2-symbol <br />
| [[BB(2)]] = 6 <br />
| [[BB(3)]] = 21<br />
| [[BB(4)]] = 107 <br />
| [[BB(5)]] = 4,098<br />
| style="background: orange;" | [[BB(6)]] > <math>2 \uparrow \uparrow \uparrow 5</math><br />
| style="background: #ffe4b2;" | [[BB(7)]] > <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> <br />
|-<br />
! 3-symbol<br />
| [[BB(2,3)]] = 38 <br />
| style="background: orange;" | [[BB(3,3)]] > <math>10^{17}</math><br />
| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>2 \uparrow\uparrow\uparrow 2^{2^{32}}</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 4-symbol <br />
| [[BB(2,4)]] = 3,932,964<br />
| style="background: #ffe4b2;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 5-symbol <br />
| style="background: orange;" | [[BB(2,5)]] > <math>10\uparrow\uparrow 4</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|-<br />
! 6-symbol <br />
| style="background: #ffe4b2;" | [[BB(2,6)]] > <math>10 \uparrow\uparrow\uparrow 3</math><br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
| style="background: #ffe4b2;" |<br />
|}<br />
<br />
In the above table, <span style="background: orange">cells are highlighted in orange</span> when there are known [[Cryptids]] (mathematically-hard machines) in that class, and <span style="background: #ffe4b2">cells are highlighted in light orange</span> when the existence of a Cryptid is given by using a known one with less states or symbols.<br />
<br />
== About bbchallenge ==<br />
[https://www.bbchallenge.org bbchallenge] is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:<br />
<br />
* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Coq_(software) Coq])<br />
* Maintaining [[Holdouts lists]] for small busy beaver values<br />
* Proving the behavior of [[:Category:Individual Machines|Individual machines]]<br />
* Finding [[Cryptids]] (mathematically-hard machines)<br />
* Searching for new [[Champions]]<br />
* Building [[Accelerated Simulator]]s to simulate halting machines faster<br />
* Writing papers and giving talks about busy beaver, see [[Papers & Talks]]<br />
<br />
In June 2024, bbchallenge achieved a significant milestone by proving in Coq / Rocq that the 5th busy beaver value, [[BB(5)]], is equal to the lower bound found in 1989: 47,176,870.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.<br />
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref><br />
<br />
== Contribute to this wiki ==<br />
This wiki is collaborative, feel free to contribute by editing existing pages or creating new ones:<br />
<br />
<inputbox><br />
type=create<br />
width=100<br />
break=no<br />
buttonlabel=Create new article<br />
default=(Article title)<br />
</inputbox><br />
<br />
==Notes==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Busy_Beaver_Functions&diff=2255Busy Beaver Functions2025-06-22T18:23:25Z<p>Xl643: </p>
<hr />
<div>The Busy Beaver Game is the search for [[Turing machine|Turing machines]] which maximize various '''Busy Beaver Functions'''. All Busy Beaver functions are non-computable. There are several, related functions with different authors referring to one or the other as "the Busy Beaver function". Therefore, it is recommended that you use a more specific designation when referring to one specific Busy Beaver function.<br />
<br />
The two most commonly used Busy Beaver functions are:<br />
<br />
* The Maximum Shift function <math>S(n, m)</math> which is the most commonly used Busy Beaver function by [[Bbchallenge.org|bbchallenge]] and is generally called <math>BB(n, m)</math> here.<br />
* The Maximum Score function <math>\Sigma(n, m)</math> which is Tibor Radó's original Busy Beaver function.<br />
where <math>n</math> denotes the number of states and <math>m</math> the number of symbols.<br />
<br />
== Max Shift Function S(n, m) ==<br />
The Maximum Shift or Maximum Step function is the largest number of steps (or shifts) that any Turing machine (of a certain size, and starting with a blank tape) takes before halting. It was introduced by Tibor Radó in his seminal Busy Beaver paper.<ref>Tibor Radó (May 1962). "[https://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf On non-computable functions]" (PDF). ''Bell System Technical Journal''. '''41''' (3): 877–884. https://doi.org/10.1002%2Fj.1538-7305.1962.tb00480.x</ref> He used the notation <math>S(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>S(n, m)</math> for <math>n</math> states and <math>m</math> symbols. Notably, the halting transition counts as a step, so the TM with rule <code>A0 -> 1RZ</code> halts in 1 step.<br />
<br />
Ben-Amram calls this the <math>time(n)</math> function.<ref name=":0">Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). [http://dx.doi.org/10.1007/BF01192693 A note on busy beavers and other creatures]. ''Mathematical Systems Theory'' '''29''' (4), July-August 1996, 375-386.</ref> Harland calls it the "frantic frog" function <math>ff(n)</math>.<ref name=":1">James Harland. [https://dl.acm.org/doi/pdf/10.5555/1151785.1151794 The Busy Beaver, the Placid Platypus and other Crazy Creatures]. 2006.</ref> <br />
<br />
In his 2020 survey, Scott Aaronson used the notation <math>BB(n, m)</math> for the Max Shift function and referred to it as "the" Busy Beaver function.<ref name=":2">Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref><br />
<br />
== Max Score Function Σ(n, m) ==<br />
The Maximum Score function is the largest number of ones (or non-zero symbols in general) left on the tape by any halting Turing machine (of a certain size, and starting with a blank tape) at the moment it halts. It was also introduced by Tibor Radó in his seminal paper. He called it the "score" of the Turing machine. He used the notation <math>\Sigma(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>\Sigma(n, m)</math> for <math>n</math> states and <math>m</math> symbols.<br />
<br />
Ben-Amram calls this the <math>ones(n)</math> function.<ref name=":0" /> Harland calls it the "busy beaver" function <math>bb(n)</math>.<ref name=":1" /> Before Aaronson's survey, this was the function that most people called "the" Busy Beaver function.<br />
<br />
== Other Busy Beaver functions ==<br />
In addition to the above functions, there are a couple of others that have appeared in the literature:<br />
<br />
* Maximum space: Ben-Amram call this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. This is the total number of tape cells read before halting. According to Ben-Amram, it includes the starting cell, but not necessarily the cell the halting transition moves to.<ref> https://link.springer.com/article/10.1007/BF01192693 created on August 1996 (unknown day in the month) </ref><br />
* Maximum consecutive ones: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.<br />
* N<sub>e</sub> function: Radó formulated the number of halting machines in terms of the set of all valid busy beaver entries M,s where s is the Turing machine, and s is the exact number of steps the halting Turing machine took. The set of all halting n-card machines is denoted E_n, and the cardinality of this set is denoted N<sub>e</sub>(n) The number of n-card Turing machines that halt after exactly or not more than s steps are respectively denoted N(s,n) and G(s,n).<br />
* Blanking busy beaver: <math>BLB(n,m)</math> is the largest of steps done by any Turing machine with n states and m symbols before blanking the tape.<br />
* [[Beeping Busy Beaver|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt|quasihalting]].<br />
* Busy periodic beaver: <math>BBP(n,m)</math> is the largest period of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.<br />
* Busy preperiodic beaver: <math>BBS(n,m)</math> is the largest preperiod of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.<br />
*BB<sub>L</sub>(n) (busy beaver for L programs):People have also studied variants with a 2-dimensional tape, or where the tape head is allowed to stay still in addition to moving left or right, etc. More broadly, given any programming language L, whose programs consist of bit-strings, one can define a Busy Beaver function for L-programs:BB<sub>L</sub>(n) := max<sub>P∈L∩{0,1}</sub><sup>≤n</sup><sub>: s(P)<∞</sub>s(P) where s(P) is the number of steps taken by P on a blank input. Alternatively, some people define a “Busy Beaver function for L-programs” using Kolmogorov complexity. That is, they let BB’<sub>L</sub>(n) be the largest integer m such that K<sub>L</sub> (m) ≤ n, where K<sub>L</sub>(m) is the length of the shortest L-program whose output is m on a blank input.<ref name=":2" /><br />
<br />
== References ==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Busy_Beaver_Functions&diff=2252Busy Beaver Functions2025-06-21T19:52:14Z<p>Xl643: /* Other Busy Beaver functions */</p>
<hr />
<div>The Busy Beaver Game is the search for [[Turing machine|Turing machines]] which maximize various '''Busy Beaver Functions'''. All Busy Beaver functions are non-computable. There are several, related functions with different authors referring to one or the other as "the Busy Beaver function". Therefore, it is recommended that you use a more specific designation when referring to one specific Busy Beaver function.<br />
<br />
The two most commonly used Busy Beaver functions are:<br />
<br />
* The Maximum Shift function <math>S(n, m)</math> which is the most commonly used Busy Beaver function by [[Bbchallenge.org|bbchallenge]] and is generally called <math>BB(n, m)</math> here.<br />
* The Maximum Score function <math>\Sigma(n, m)</math> which is Tibor Radó's original Busy Beaver function.<br />
where <math>n</math> denotes the number of states and <math>m</math> the number of symbols.<br />
<br />
== Max Shift Function S(n, m) ==<br />
The Maximum Shift or Maximum Step function is the largest number of steps (or shifts) that any Turing machine (of a certain size, and starting with a blank tape) takes before halting. It was introduced by Tibor Radó in his seminal Busy Beaver paper.<ref>Tibor Radó (May 1962). "[https://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf On non-computable functions]" (PDF). ''Bell System Technical Journal''. '''41''' (3): 877–884. https://doi.org/10.1002%2Fj.1538-7305.1962.tb00480.x</ref> He used the notation <math>S(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>S(n, m)</math> for <math>n</math> states and <math>m</math> symbols. Notably, the halting transition counts as a step, so the TM with rule <code>A0 -> 1RZ</code> halts in 1 step.<br />
<br />
Ben-Amram calls this the <math>time(n)</math> function.<ref name=":0">Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). [http://dx.doi.org/10.1007/BF01192693 A note on busy beavers and other creatures]. ''Mathematical Systems Theory'' '''29''' (4), July-August 1996, 375-386.</ref> Harland calls it the "frantic frog" function <math>ff(n)</math>.<ref name=":1">James Harland. [https://dl.acm.org/doi/pdf/10.5555/1151785.1151794 The Busy Beaver, the Placid Platypus and other Crazy Creatures]. 2006.</ref> <br />
<br />
In his 2020 survey, Scott Aaronson used the notation <math>BB(n, m)</math> for the Max Shift function and referred to it as "the" Busy Beaver function.<ref>Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref><br />
<br />
== Max Score Function Σ(n, m) ==<br />
The Maximum Score function is the largest number of ones (or non-zero symbols in general) left on the tape by any halting Turing machine (of a certain size, and starting with a blank tape) at the moment it halts. It was also introduced by Tibor Radó in his seminal paper. He called it the "score" of the Turing machine. He used the notation <math>\Sigma(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>\Sigma(n, m)</math> for <math>n</math> states and <math>m</math> symbols.<br />
<br />
Ben-Amram calls this the <math>ones(n)</math> function.<ref name=":0" /> Harland calls it the "busy beaver" function <math>bb(n)</math>.<ref name=":1" /> Before Aaronson's survey, this was the function that most people called "the" Busy Beaver function.<br />
<br />
== Other Busy Beaver functions ==<br />
In addition to the above functions, there are a couple of others that have appeared in the literature:<br />
<br />
* Maximum space: Ben-Amram call this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. This is the total number of tape cells read before halting. According to Ben-Amram, it includes the starting cell, but not necessarily the cell the halting transition moves to.<ref> https://link.springer.com/article/10.1007/BF01192693 created on August 1996 (unknown day in the month) </ref><br />
* Maximum consecutive ones: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.<br />
* N<sub>e</sub> function: Radó formulated the number of halting machines in terms of the set of all valid busy beaver entries M,s where s is the Turing machine, and s is the exact number of steps the halting Turing machine took. The set of all halting n-card machines is denoted E_n, and the cardinality of this set is denoted N<sub>e</sub>(n) The number of n-card Turing machines that halt after exactly or not more than s steps are respectively denoted N(s,n) and G(s,n).<br />
* Blanking busy beaver: <math>BLB(n,m)</math> is the largest of steps done by any Turing machine with n states and m symbols before blanking the tape.<br />
* [[Beeping Busy Beaver|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt|quasihalting]].<br />
* Busy periodic beaver: <math>BBP(n,m)</math> is the largest period of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.<br />
* Busy preperiodic beaver: <math>BBS(n,m)</math> is the largest preperiod of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.<br />
*BB<sub>L</sub>(n) (busy beaver for L programs):People have also studied variants with a 2-dimensional tape, or where the tape head is allowed to stay still in addition to moving left or right, etc. More broadly, given any programming language L, whose programs consist of bit-strings, one can define a Busy Beaver function for L-programs:BB<sub>L</sub>(n) := max<sub>P∈L∩{0,1}</sub><sup>≤n</sup><sub>: s(P)<∞</sub>s(P) where s(P) is the number of steps taken by P on a blank input. Alternatively, some people define a “Busy Beaver function for L-programs” using Kolmogorov complexity. That is, they let BB’<sub>L</sub>(n) be the largest integer m such that K<sub>L</sub> (m) ≤ n, where K<sub>L</sub>(m) is the length of the shortest L-program whose output is m on a blank input.<ref>[https://www.scottaaronson.com/papers/bb.pdf Scott Aaronson - The Busy Beaver frontier]</ref><br />
<br />
== References ==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Busy_Beaver_Functions&diff=2251Busy Beaver Functions2025-06-21T19:44:59Z<p>Xl643: /* Other Busy Beaver functions */</p>
<hr />
<div>The Busy Beaver Game is the search for [[Turing machine|Turing machines]] which maximize various '''Busy Beaver Functions'''. All Busy Beaver functions are non-computable. There are several, related functions with different authors referring to one or the other as "the Busy Beaver function". Therefore, it is recommended that you use a more specific designation when referring to one specific Busy Beaver function.<br />
<br />
The two most commonly used Busy Beaver functions are:<br />
<br />
* The Maximum Shift function <math>S(n, m)</math> which is the most commonly used Busy Beaver function by [[Bbchallenge.org|bbchallenge]] and is generally called <math>BB(n, m)</math> here.<br />
* The Maximum Score function <math>\Sigma(n, m)</math> which is Tibor Radó's original Busy Beaver function.<br />
where <math>n</math> denotes the number of states and <math>m</math> the number of symbols.<br />
<br />
== Max Shift Function S(n, m) ==<br />
The Maximum Shift or Maximum Step function is the largest number of steps (or shifts) that any Turing machine (of a certain size, and starting with a blank tape) takes before halting. It was introduced by Tibor Radó in his seminal Busy Beaver paper.<ref>Tibor Radó (May 1962). "[https://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf On non-computable functions]" (PDF). ''Bell System Technical Journal''. '''41''' (3): 877–884. https://doi.org/10.1002%2Fj.1538-7305.1962.tb00480.x</ref> He used the notation <math>S(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>S(n, m)</math> for <math>n</math> states and <math>m</math> symbols. Notably, the halting transition counts as a step, so the TM with rule <code>A0 -> 1RZ</code> halts in 1 step.<br />
<br />
Ben-Amram calls this the <math>time(n)</math> function.<ref name=":0">Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). [http://dx.doi.org/10.1007/BF01192693 A note on busy beavers and other creatures]. ''Mathematical Systems Theory'' '''29''' (4), July-August 1996, 375-386.</ref> Harland calls it the "frantic frog" function <math>ff(n)</math>.<ref name=":1">James Harland. [https://dl.acm.org/doi/pdf/10.5555/1151785.1151794 The Busy Beaver, the Placid Platypus and other Crazy Creatures]. 2006.</ref> <br />
<br />
In his 2020 survey, Scott Aaronson used the notation <math>BB(n, m)</math> for the Max Shift function and referred to it as "the" Busy Beaver function.<ref>Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref><br />
<br />
== Max Score Function Σ(n, m) ==<br />
The Maximum Score function is the largest number of ones (or non-zero symbols in general) left on the tape by any halting Turing machine (of a certain size, and starting with a blank tape) at the moment it halts. It was also introduced by Tibor Radó in his seminal paper. He called it the "score" of the Turing machine. He used the notation <math>\Sigma(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>\Sigma(n, m)</math> for <math>n</math> states and <math>m</math> symbols.<br />
<br />
Ben-Amram calls this the <math>ones(n)</math> function.<ref name=":0" /> Harland calls it the "busy beaver" function <math>bb(n)</math>.<ref name=":1" /> Before Aaronson's survey, this was the function that most people called "the" Busy Beaver function.<br />
<br />
== Other Busy Beaver functions ==<br />
In addition to the above functions, there are a couple of others that have appeared in the literature:<br />
<br />
* Maximum space: Ben-Amram call this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. This is the total number of tape cells read before halting. According to Ben-Amram, it includes the starting cell, but not necessarily the cell the halting transition moves to.<ref> https://link.springer.com/article/10.1007/BF01192693 created on August 1996 (unknown day in the month) </ref><br />
* Maximum consecutive ones: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.<br />
* N<sub>e</sub> function: Radó formulated the number of halting machines in terms of the set of all valid busy beaver entries M,s where s is the Turing machine, and s is the exact number of steps the halting Turing machine took. The set of all halting n-card machines is denoted E_n, and the cardinality of this set is denoted N<sub>e</sub>(n) The number of n-card Turing machines that halt after exactly or not more than s steps are respectively denoted N(s,n) and G(s,n).<br />
* Blanking busy beaver: <math>BLB(n,m)</math> is the largest of steps done by any Turing machine with n states and m symbols before blanking the tape.<br />
* [[Beeping Busy Beaver|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt|quasihalting]].<br />
* Busy periodic beaver: <math>BBP(n,m)</math> is the largest period of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.<br />
* Busy preperiodic beaver: <math>BBS(n,m)</math> is the largest preperiod of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.<br />
<br />
== References ==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Busy_Beaver_Functions&diff=2248Busy Beaver Functions2025-06-20T22:18:03Z<p>Xl643: I added more</p>
<hr />
<div>The Busy Beaver Game is the search for [[Turing machine|Turing machines]] which maximize various '''Busy Beaver Functions'''. All Busy Beaver functions are non-computable. There are several, related functions with different authors referring to one or the other as "the Busy Beaver function". Therefore, it is recommended that you use a more specific designation when referring to one specific Busy Beaver function.<br />
<br />
The two most commonly used Busy Beaver functions are:<br />
<br />
* The Maximum Shift function <math>S(n, m)</math> which is the most commonly used Busy Beaver function by [[Bbchallenge.org|bbchallenge]] and is generally called <math>BB(n, m)</math> here.<br />
* The Maximum Score function <math>\Sigma(n, m)</math> which is Tibor Radó's original Busy Beaver function.<br />
where <math>n</math> denotes the number of states and <math>m</math> the number of symbols.<br />
<br />
== Max Shift Function S(n, m) ==<br />
The Maximum Shift or Maximum Step function is the largest number of steps (or shifts) that any Turing machine (of a certain size, and starting with a blank tape) takes before halting. It was introduced by Tibor Radó in his seminal Busy Beaver paper.<ref>Tibor Radó (May 1962). "[https://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf On non-computable functions]" (PDF). ''Bell System Technical Journal''. '''41''' (3): 877–884. https://doi.org/10.1002%2Fj.1538-7305.1962.tb00480.x</ref> He used the notation <math>S(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>S(n, m)</math> for <math>n</math> states and <math>m</math> symbols. Notably, the halting transition counts as a step, so the TM with rule <code>A0 -> 1RZ</code> halts in 1 step.<br />
<br />
Ben-Amram calls this the <math>time(n)</math> function.<ref name=":0">Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). [http://dx.doi.org/10.1007/BF01192693 A note on busy beavers and other creatures]. ''Mathematical Systems Theory'' '''29''' (4), July-August 1996, 375-386.</ref> Harland calls it the "frantic frog" function <math>ff(n)</math>.<ref name=":1">James Harland. [https://dl.acm.org/doi/pdf/10.5555/1151785.1151794 The Busy Beaver, the Placid Platypus and other Crazy Creatures]. 2006.</ref> <br />
<br />
In his 2020 survey, Scott Aaronson used the notation <math>BB(n, m)</math> for the Max Shift function and referred to it as "the" Busy Beaver function.<ref>Scott Aaronson. [https://scottaaronson.blog/?p=4916 The Busy Beaver Frontier]. 2020.</ref><br />
<br />
== Max Score Function Σ(n, m) ==<br />
The Maximum Score function is the largest number of ones (or non-zero symbols in general) left on the tape by any halting Turing machine (of a certain size, and starting with a blank tape) at the moment it halts. It was also introduced by Tibor Radó in his seminal paper. He called it the "score" of the Turing machine. He used the notation <math>\Sigma(n)</math> to define it for Turing machines with <math>n</math> states and 2 symbols. This was later extended to <math>\Sigma(n, m)</math> for <math>n</math> states and <math>m</math> symbols.<br />
<br />
Ben-Amram calls this the <math>ones(n)</math> function.<ref name=":0" /> Harland calls it the "busy beaver" function <math>bb(n)</math>.<ref name=":1" /> Before Aaronson's survey, this was the function that most people called "the" Busy Beaver function.<br />
<br />
== Other Busy Beaver functions ==<br />
In addition to the above functions, there are a couple of others that have appeared in the literature:<br />
<br />
* Maximum space: Ben-Amram call this <math>space(n)</math><ref name=":0" />, bbchallenge calls it <code>BB_SPACE(n)</code> or <math>BB_{space}(n)</math>. This is the total number of tape cells read before halting. According to Ben-Amram, it includes the starting cell, but not necessarily the cell the halting transition moves to.<ref> https://link.springer.com/article/10.1007/BF01192693 created on August 1996 (unknown day in the month) </ref><br />
* Maximum consecutive ones: Ben-Amram calls this <math>num(n)</math>.<ref name=":0" /> A TM only qualifies if it halts with all ones consecutive on tape.<br />
*ones(n): Consider Turing machines that read and write the symbols 1 and 0 on a one-dimensional tape that is infinite in both directions, and halt when started on a tape containing all O's. ones(n) is the maximum number of 1's such a machine, with states, may leave on its tape when it halts.<br />
* Blanking busy beaver: <math>BLB(n,m)</math> is the largest of steps done by any Turing machine with n states and m symbols before blanking the tape.<br />
* [[Beeping Busy Beaver|Beeping busy beaver]]: <math>BBB(n,m)</math> is the largest of steps done by any Turing machine with ''n'' states and ''m'' symbols before [[Quasihalt|quasihalting]].<br />
* Busy periodic beaver: <math>BBP(n,m)</math> is the largest period of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.<br />
* Busy preperiodic beaver: <math>BBS(n,m)</math> is the largest preperiod of any cycler or [[translated cycler]] with ''n'' states and ''m'' symbols.<br />
<br />
== References ==<br />
<references /></div>Xl643https://wiki.bbchallenge.org/w/index.php?title=User:Xl643&diff=2161User:Xl6432025-06-08T06:49:18Z<p>Xl643: Created page with "Poo"</p>
<hr />
<div>Poo</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=BB(8)&diff=1962BB(8)2025-05-19T01:03:05Z<p>Xl643: Created page with "BB(8) is a 8 state, 2 symbol Turing machine, the current BB(8) champion is [insert]"</p>
<hr />
<div>BB(8) is a 8 state, 2 symbol Turing machine, the current BB(8) champion is [insert]</div>Xl643https://wiki.bbchallenge.org/w/index.php?title=Beeping_Busy_Beaver&diff=1960Beeping Busy Beaver2025-05-18T23:29:08Z<p>Xl643: </p>
<hr />
<div>The '''Beeping Busy Beaver''' (BBB) function is a variant of the [[Busy Beaver Functions|Busy Beaver function]] proposed by Scott Aaronson in his 2020 "The Busy Beaver Frontier" survey.<ref name=":0">Scott Aaronson. "The Busy Beaver Frontier". https://www.scottaaronson.com/papers/bb.pdf</ref> It is notable because it is uncomputable even if you have access to a halting oracle for Turing Machines.<br />
<br />
== Definition ==<br />
Consider a ''beeping Turing machine'', which is a [[Turing machine]] that has a special state named "beep state". Every time the TM enters the "beep state" it ''beeps''. There are two possibilities, either this TM beeps a finite number of times (and thus there is a final beep) or it never stops beeping. Nick Drozd coined the term [[Quasihalt|quasihalting]] to describe the event when a TM last beeps. A TM quasihalts if it beeps only a finite number of times.<ref>Nick Drozd. Beeping Busy Beavers. https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.html</ref> The Beeping Busy Beaver problem is analogous to the Busy Beaver problem, replacing halting with quasihalting. In other words, let <math>b(M)</math> be the number of steps the machine M takes until it quasihalts (beeps for the last time) if it quasihalts (we will say <math>b(M) = \infty</math> if the TM never stops beeping). Then<br />
<br />
<math display="block">\operatorname{BBB}(n) := \max_{{M \in T(n)\ :\ b(M) < \infty}} b(M)</math><br />
<br />
where <math>T(n)</math> is the set of Turing machines with <math>n</math> states and two symbols.<br />
<br />
Note that these Turing machines need not ever halt, so the [[Tree Normal Form]] algorithm needs to be modified (to allow TMs with no halt transitions) when searching for BBB champions.<br />
<br />
== Significance ==<br />
<br />
It is easy to see that <math>\operatorname{BBB}(n) \ge \operatorname{BB}(n)</math>, by letting the beep state be the state that is reached immediately before the halt state.<br />
<br />
Values <math>> \operatorname{BB}(n)</math> may occur when the machine emits a beep before entering non-halting behavior.<br />
<br />
Moreover, it turns out that <math>\operatorname{BBB}</math> grows uncomputably faster than <math>\operatorname{BB}</math> (as fast as BB augmented with a halting oracle).<br />
<br />
== Results ==<br />
<br />
* BBB(1) = 1<ref name=":0" /><br />
* BBB(2) = 6<ref name=":0" /><br />
* BBB(3) = 55<br />
* BBB(4) ≥ 32,779,478<br />
* BBB(5) ≥ 10<sup>14,006</sup><ref>Nick Drozd. https://scottaaronson.blog/?p=8088#comment-1981333</ref> and probably <math>BBB(5) \ge 10^{10^{10^5}}</math> due to a "[[probviously]]" halting [[Cryptids|Cryptid]].<ref>Shawn Ligocki. Mother of Giants.https://www.sligocki.com/2022/04/03/mother-of-giants.html</ref><br />
<br />
All known champions quasihalt by becoming [[Translated Cycler|Translated Cyclers]], a property which is known to be weaker than the general quasihalting condition.<br />
<br />
== References ==<br />
<br />
[[category:Functions]]</div>Xl643