BB(2,5): Difference between revisions
(Add cryptids section, holdouts section) |
(wikify TMs, add some links and mention the champ is a shift-overflow counter.) |
||
| Line 1: | Line 1: | ||
The 2-state, 5-symbol Busy Beaver problem '''BB(2,5)''' is unsolved. With the discovery of the [[Cryptids|Cryptid]] machine [[Hydra]] by Daniel Yuan in April 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(2,5) and thus [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2,5) is Hard]. | The 2-state, 5-symbol Busy Beaver problem '''BB(2,5)''' is unsolved. With the discovery of the [[Cryptids|Cryptid]] machine [[Hydra]] by Daniel Yuan in April 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(2,5) and thus [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2,5) is Hard]. | ||
The current BB(2,5) champion is {{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ|halt}}, also discovered by Daniel Yuan in June 2024. It is notable for being the only champion machine that exhibits [[Counter]] behavior. It provides the lower bound: | The current BB(2,5) champion is {{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ|halt}}, also discovered by Daniel Yuan in June 2024. It is notable for being the only champion machine that exhibits [[Counter]] behavior and specifically a halting [[shift overflow counter]]. It provides the lower bound: | ||
<math display="block">S(2,5) > \Sigma(2,5) > 10^{10^{10^{3\,314\,360}}} > 10 \uparrow\uparrow 4</math> | <math display="block">S(2,5) > \Sigma(2,5) > 10^{10^{10^{3\,314\,360}}} > 10 \uparrow\uparrow 4</math> | ||
== Cryptids == | == Cryptids == | ||
Known BB(2,5) Cryptids | Known BB(2,5) Cryptids | ||
* 1RB3RB---3LA1RA_2LA3RA4LB0LB0LA, known as Hydra. | * {{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}, known as [[Hydra]]. | ||
* 1RB3RB---3LA1RA_2LA3RA4LB0LB1LB, known as the bonus cryptid. | * {{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB1LB}}, known as the bonus cryptid. | ||
== Holdouts == | == Holdouts == | ||
Justin Blanchard generated a list of 499 holdouts in May 2024, which was cut down to 273 by an application of deciders written for BB(6), then again to 217 using CTL by the end of June 2024. This list of holdouts can be found [[:File:2x5 holdouts 217.txt|here]]. Since then, between 50 and 100 machines have been claimed to have been solved, but no new reduced holdout list has been generated. | Justin Blanchard generated a list of 499 holdouts in May 2024, which was cut down to 273 by an application of deciders written for BB(6), then again to 217 using CTL by the end of June 2024. This list of holdouts can be found [[:File:2x5 holdouts 217.txt|here]]. Since then, between 50 and 100 machines have been claimed to have been solved, but no new reduced holdout list has been generated. | ||
[[Category:BB Domain]] | [[Category:BB Domain]] | ||
Revision as of 19:34, 7 February 2025
The 2-state, 5-symbol Busy Beaver problem BB(2,5) is unsolved. With the discovery of the Cryptid machine Hydra by Daniel Yuan in April 2024, we now know that we must solve a Collatz-like problem in order to solve BB(2,5) and thus BB(2,5) is Hard.
The current BB(2,5) champion is 1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ (bbch), also discovered by Daniel Yuan in June 2024. It is notable for being the only champion machine that exhibits Counter behavior and specifically a halting shift overflow counter. It provides the lower bound:
Cryptids
Known BB(2,5) Cryptids
1RB3RB---3LA1RA_2LA3RA4LB0LB0LA(bbch), known as Hydra.1RB3RB---3LA1RA_2LA3RA4LB0LB1LB(bbch), known as the bonus cryptid.
Holdouts
Justin Blanchard generated a list of 499 holdouts in May 2024, which was cut down to 273 by an application of deciders written for BB(6), then again to 217 using CTL by the end of June 2024. This list of holdouts can be found here. Since then, between 50 and 100 machines have been claimed to have been solved, but no new reduced holdout list has been generated.