## Reference

Scott Aaronson“The Busy Beaver Frontier” (2020) // ACM SIGACT News. Vol. 51. No 3. Pp. 32–54. 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?

## Bib

```
@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}
}
```