“The Busy Beaver Frontier”, 2019-08-28 (; backlinks; similar):
The 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) > 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? [cf. “Collatz-like behavior of Busy Beavers” & FRACTRAN & “Maybe the Spaghetti Code Conjecture is False”/“A Busy Beaver Champion Program Derived from Scratch”.]
View PDF: