Skip to main content
3 of 4
http -> https (the question was bumped anyway)
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Let's note that this is not a question of whether Collatz is undecidable. The statement $\neg\mathrm{Con}(PA)$ is undecidable (by $PA$, assuming $PA$ is consistent) but nevertheless $\neg\mathrm{Con}(PA)$ is provably equivalent to a certain Turing machine halting (the one that searches for a proof of a contradiction in PA).

Rather, the question is whether

there is a $\Pi^0_1$ statement $\varphi$ such that the Collatz problem, which on its face is $\Pi^0_2$, is already known to be equivalent to $\varphi$.

Here already known means in particular that we are not allowed to assume that Collatz is or is not provable or disprovable in any particular system, unless we already know that.

The best evidence that there is no such $\varphi$ seems to be in the paper mentioned by @Burak:

Kurtz, Stuart A.; Simon, Janos, The undecidability of the generalized Collatz problem, Cai, Jin-Yi (ed.) et al., Theory and applications of models of computation. 4th international conference, TAMC 2007, Shanghai, China, May 22--25, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72503-9/pbk). Lecture Notes in Computer Science 4484, 542-553 (2007). ZBL1198.03043, MR2374341.

Namely, they give a parametrized family of similar problems such that the collection of parameters for which Collatz-for-those-parameters is true, is $\Pi^0_2$-complete and hence not $\Pi^0_1$.

They can do this without thereby solving the Collatz problem, just like Matiyasevich et al. could show that solvability of diophantine equation was $\Sigma^0_1$-complete, without thereby solving any particular equation themselves.

If Collatz could somehow be simplified to a $\Pi^0_1$ form then quite plausibly the generalized version could too by the same argument (whatever that hypothetical argument would be) but that Kurtz and Simon show will not happen.

Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114