The beeping busy beaver function is a relative of the maximum shifts function[note 1] proposed by Scott Aaronson in a conversation with Harvey Friedman[1]. Define a beep state as a state that is only exited a finite amount of times. Then for a Turing machine M, b(M) is the number of the last step on which it exits a beep state. BBB(n) is the maximum value of b(M) if M is a n-state Turing machine.

Known values and bounds

  • BBB(1) = 1
  • BBB(2) = 6
  • BBB(3) ≥ 55
  • BBB(4) ≥ 66349[2]

Footnotes

  1. Aaronson refers to the maximum shifts function as the "busy beaver function", a term which on this wiki usually refers to the sigma function.

References

  1. https://www.scottaaronson.com/papers/bb.pdf (retrieved 2021-03-03)
  2. nickdrozd, Beeping Busy Beavers, Github page. (retrieved 2021-03-03)
Community content is available under CC-BY-SA unless otherwise noted.