5-state busy beaver winner

From BusyBeaverWiki
Revision as of 15:36, 10 September 2024 by Sligocki (talk | contribs)
Jump to navigation Jump to search

The 5-state busy beaver (BB(5)) champion (and winner!) is: 1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA (bbch). 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 BB(5)≥47,176,870 and Σ(5)≥4098.

Behavior

This machine repeatedly applies the following Collatz-like map, starting with x=0[2]: g(x)→5x+183if x≡0(mod3)g(x)→5x+223if x≡1(mod3)g(x)→HALTif x≡2(mod3)which can alternatively be written as[3]:

g(3k)→5k+6g(3k+1)→5k+9g(3k+2)→HALT

The full orbit from x=0 is: 0→6→16→34→64→114→196→334→564→946→1584→2646→4416→7366→12284→HALT

References

  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