Answers are grounded in this paper and cite their sources.
Reveals connections between the halting problem and computational complexity of the Collatz conjecture, suggesting implications for reverse mathematics.
We investigate the computational complexity of the Collatz ($3n+1$) conjecture via computability theory and reverse mathematics. Let LC denote the set of integers whose Collatz orbits reach $1$. We show that a many-one reduction from the halting problem to LC is incompatible with the truth of the conjecture, since decidability would follow. In the event the conjecture is false, we identify three independent barriers to such a reduction: a parity bottleneck restricting computational branching, an information-theoretic entropy bound from the golden-mean subshift, and a degree-theoretic gap requiring oracle power beyond the halting problem. We introduce the Collatz Choice Principle (CC), asserting that the set of counterexamples is Turing-equivalent to the halting problem, and prove that CC is necessary and sufficient for a many-one reduction from the halting problem to LC. We further show that CC has the strength of ACA₀ in reverse mathematics. This reframes the complexity of the Collatz problem as an axiomatic question about the consistency and independence of CC over ZFC.
No takes yet. Share an insight, caveat, or question.
Ashish Paudel (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: