5-state busy beaver winner: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
mNo edit summary
(Add Michel version of formula (which I think is much simpler).)
Line 2: Line 2:
The 5-state busy beaver champion (and winner!) is: [https://bbchallenge.org/1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA&status=halt https://bbchallenge.org/1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA]. It was found by Heiner Marxen and Jürgen Buntrock in 1989<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref>. The machine halts after 47,176,870 steps and with 4098 1's on the tape, showing that <math>BB(5) \ge 47,176,870</math> and <math>\Sigma(5) \ge 4098</math>.
The 5-state busy beaver champion (and winner!) is: [https://bbchallenge.org/1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA&status=halt https://bbchallenge.org/1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA]. It was found by Heiner Marxen and Jürgen Buntrock in 1989<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref>. The machine halts after 47,176,870 steps and with 4098 1's on the tape, showing that <math>BB(5) \ge 47,176,870</math> and <math>\Sigma(5) \ge 4098</math>.


== Behavior ==
This machine repeatedly applies the following map, starting with <math>x = 0</math><ref>Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf</ref>:
This machine repeatedly applies the following map, starting with <math>x = 0</math><ref>Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf</ref>:
<math display="block">\begin{align}
<math display="block">\begin{align}
Line 7: Line 8:
   g(x) & \to \frac{5x+22}{3} && \text{if }x \equiv 1 \pmod{3} \\
   g(x) & \to \frac{5x+22}{3} && \text{if }x \equiv 1 \pmod{3} \\
   g(x) & \to \text{HALT}    && \text{if }x \equiv 2 \pmod{3}
   g(x) & \to \text{HALT}    && \text{if }x \equiv 2 \pmod{3}
\end{align}</math>which can alternatively be written as<ref>Pascal Michel. Behavior of busy beavers.https://bbchallenge.org/~pascal.michel/beh#tm52a</ref>:
<math display="block">\begin{align}
  g(3k)  & \to 5k+6 \\
  g(3k+1) & \to 5k+9 \\
  g(3k+2) & \to \text{HALT} \\
\end{align}</math>
\end{align}</math>



Revision as of 03:03, 10 July 2024

The 5-state busy beaver champion (and winner!) is: https://bbchallenge.org/1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA. It was found by Heiner Marxen and Jürgen Buntrock in 1989[1]. The machine halts after 47,176,870 steps and with 4098 1's on the tape, showing that and .

Behavior

This machine repeatedly applies the following map, starting with [2]:

which can alternatively be written as[3]:

The full orbit from is:

  1. H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html
  2. Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf
  3. Pascal Michel. Behavior of busy beavers.https://bbchallenge.org/~pascal.michel/beh#tm52a