On the hardness of knowing busy beaver values BB(15) and BB(5,4)
share
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, and BB(n,k) denotes its k-symbol generalisation to k≥ 2. The busy beaver function n ↦BB(n) is uncomputable and its values have been linked to hard open problems in mathematics and notions of unprovability. In this paper, we show that there are two explicit Turing machines, one with 15 states and 2 symbols, the other with 5 states and 4 symbols, that halt if and only if the following Collatz-related conjecture by Erdős [1979] does not hold does not hold: for all n>8 there is at least one digit 2 in the base 3 representation of 2^n. This result implies that knowing the values of BB(15) or BB(5,4) is at least as hard as solving Erdős' conjecture and makes, to date, BB(15) the smallest busy beaver value that is related to a natural open problem in mathematics. For comparison, Yedidia and Aaronson [2016] show that knowing BB(4,888) and BB(5,372) are as hard as solving Goldbach's conjecture and the Riemann hypothesis, respectively (later informally improved to BB(27) and BB(744)). Finally, our result puts a finite, albeit large, bound on Erdős' conjecture, by making it equivalent to the following finite statement: for all 8 < n ≤min(BB(15), BB(5,4)) there is at least one digit 2 in the base 3 representation of 2^n.
READ FULL TEXT