Measuring Decidability as Related to Busy Beaver Numbers
Provides a novel theoretical framework for classifying conjectures by the minimum number of Turing machine states needed to model them, but remains a conceptual proposal without empirical validation.
The paper introduces a new notion of decidability based on Busy Beaver numbers, constructing explicit Turing machines for Brocard's problem and Fermat primes that halt only if solutions exist.
The theoretical existence of Busy Beaver numbers provides a new notion for decidability and corresponding heuristic for conjectures. The minimum number of states in which a conjecture can be modeled gives a classification of what logic system can describe said conjecture. In this work, we construct explicit Turing machines that search for a solution to Brocard's problem greater than 7 and a Fermat prime beyond the 4th which halt if and only if such a solution exists.