Busy Beaver Frontier

The Busy Beaver Frontier was a Busy Beaver survey article published by Scott Aaronson in 2020. It describes the Busy Beaver problem, introduced a number of variants (such as the Lazy Beaver and Beeping Busy Beaver) and made a number of conjectures. This article introduced many new people to the Busy Beaver problem and was a major inspiration for the bbchallenge community.

Conjectures

• Conjecture 10: BB(5) = 47,176,870. Proven by bbchallenge in 2024.
• Conjecture 11: ZF cannot prove the value of BB(20). See Independence from ZFC.
• Conjecture 12: PA cannot prove the value of BB(10).
• Conjecture 13: There exists a $n_0$ such that for all $n\ge n_0$: $BB(n+1)>2^{BB(n)}$.
• Conjecture 18: $BB(n)<\mathrm{\Sigma }(n+1)$ for all $n\ge 4$.
• Conjecture 19: $\underset{n\to \mathrm{\infty }}{\lim }\frac{\log BB(n)}{\log \mathrm{\Sigma }(n)}=2$
• Conjecture 22: The function $g$ defined in 5-state busy beaver winner eventually terminates for all starting numbers.
• Conjecture 23: For all $n\ge 3$, there is an "essentially unique" n-state Busy Beaver.
• Conjecture 24: Every Busy Beaver Turing machine, viewed as a directed graph, is strongly connected.
• Conjecture 25: $LB(n)\ge \frac{D(n)}{n^{O(1)}}$ where LB is the Lazy Beaver function, D(n) is the number of "essentially different" n-state TMs.