Hardness of Busy Beaver Value BB(15)

The busy beaver value BB(n) is the maximum number of steps made by any n-state, 2-symbol deterministic halting Turing machine starting on blank tape. The busy beaver function \(n \mapsto \text {BB}(n)\) is uncomputable and, from below, only 4 of its values, \(\text {BB}(1)\, \dots \, \text {BB}(4)\) , are known to date. This leads one to ask: from above, what is the smallest BB value that encodes a major mathematical challenge? Knowing BB(4,888) has been shown by Yedidia and Aaronson [32] to be at least as hard as solving Goldbach’s conjecture, with a subsequent improvement, as yet unpublished, to BB(27) [2, 6]. We prove that knowing BB(15) is at least as hard as solving the following Collatz-related conjecture by Erdős, open since 1979 [10]: for all \(n>8\) there is at least one digit 2 in the base 3 representation of \(2^n\) . We do so by constructing an explicit 15-state, 2-symbol Turing machine that halts if and only if the conjecture is false. This 2-symbol Turing machine simulates a conceptually simpler 5-state, 4-symbol machine which we construct first. This makes, to date, BB(15) the smallest busy beaver value that is related to a natural open problem in mathematics, bringing to light one of the many challenges underlying the quest of knowing busy beaver values.