The Busy Beaver Frontier

Scott Aaronson · 2020
DOI: 10.1145/3427361.3427369

Abstract

The Busy Beaver function, with its incomprehensibly rapid growth, has captivated generations of computer scientists, mathematicians, and hobbyists. In this survey, I o er a personal view of the BB function 58 years after its introduction, emphasizing lesser-known insights, recent progress, and especially favorite open problems. Examples of such problems include: when does the BB function rst exceed the Ackermann function? Is the value of BB(20) independent of set theory? Can we prove that BB(n + 1) \textgreater 2BB(n) for large enough n? Given BB(n), how many advice bits are needed to compute BB(n + 1)? Do all Busy Beavers halt on all inputs, not just the 0 input? Is it decidable, given n, whether BB(n) is even or odd?

Reference

Scott Aaronson “The Busy Beaver Frontier” (2020) DOI: 10.1145/3427361.3427369

@Article{aaronson2020,
  title = {The Busy Beaver Frontier},
  volume = {51},
  issn = {0163-5700},
  url = {https://dl.acm.org/doi/10.1145/3427361.3427369},
  doi = {10.1145/3427361.3427369},
  abstract = {The Busy Beaver function, with its incomprehensibly rapid growth, has captivated generations of computer scientists, mathematicians, and hobbyists. In this survey, I o er a personal view of the BB function 58 years after its introduction, emphasizing lesser-known insights, recent progress, and especially favorite open problems. Examples of such problems include: when does the BB function rst exceed the Ackermann function? Is the value of BB(20) independent of set theory? Can we prove that BB(n + 1) \textgreater 2BB(n) for large enough n? Given BB(n), how many advice bits are needed to compute BB(n + 1)? Do all Busy Beavers halt on all inputs, not just the 0 input? Is it decidable, given n, whether BB(n) is even or odd?},
  language = {en},
  number = {3},
  urldate = {2022-05-29},
  journal = {ACM SIGACT News},
  author = {Aaronson, Scott},
  month = {sep},
  year = {2020},
  pages = {32--54}
}