2021/07/26 by Tristan Stérin, Stérin, Tristan, Damien Woods +1
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #F.1 #F.1.1 #F.1.3 #F.4.1 #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)
paper · pdf · doi:10.48550/arxiv.2107.12475
openalex publication_date 2021/07/26 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
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 ↦ BB(n) is uncomputable and, from below, only 4 of its values, BB(1) ... 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 [28] to be at least as hard as solving Goldbach's conjecture, with a subsequent improvement, as yet unpublished, to BB(27) [4,1]. We prove that knowing BB(15) is at least as hard as solving the following Collatz-related conjecture by Erdős, open since 1979 [9]: for all n > 8 there is at least one digit 2 in the base 3 representation of 2n. 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.