ECCC-Report TR20-115https://eccc.weizmann.ac.il/report/2020/115Comments and Revisions published for TR20-115en-usSat, 01 Aug 2020 08:13:00 +0300
Paper TR20-115
| The Busy Beaver Frontier |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2020/115The Busy Beaver function, with its incomprehensibly rapid growth, has captivated generations of computer scientists, mathematicians, and hobbyists. In this survey, I offer 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 first exceed the Ackermann function? Is the value of BB(20) independent of set theory? Can we prove that BB(n+1)>2^BB(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?Sat, 01 Aug 2020 08:13:00 +0300https://eccc.weizmann.ac.il/report/2020/115