Is there a known Turing machine which halts if and only if the Collatz conjecture has a counterexample?

Question

Some of the simplest and most interesting unproved conjectures in mathematics are Goldbach's conjecture, the Riemann hypothesis, and the Collatz conjecture.

Goldbach's conjecture asserts that every even number greater than or equal to 4 can be written as the sum of two prime numbers. It's pretty straightforward how to create a computer program which halts if and only if there exists a counterexample to Goldbach's conjecture: simply loop over all integers, test if each one is a counterexample, and halt if a counterexample is found.

For the Riemann hypothesis, there's also a "known" computer program which halts if and only if there exists a counterexample.

(Given the usual statement of the Riemann hypothesis, this is not so clear, but Jeffrey C. Lagarias' paper "An Elementary Problem Equivalent to the Riemann Hypothesis" shows that the Riemann hypothesis is equivalent to the statement that a certain sequence of integers $L$ is a lower bound for a certain sequence of real numbers $R$. The sequence $L$ is computable, and $R$ is computable to arbitrary precision, so our computer program only needs to compute all elements of $R$ in parallel, and halt if any element is ever discovered to be smaller than its corresponding element in $L$.)

But how about the Collatz conjecture?

The Collatz conjecture states that for all positive integers $n$, the "hailstone sequence" $H_n$ eventually reaches $1$.

We could try to do the same thing we did with Goldbach's conjecture: loop over all positive integers $n$ and halt if a counterexample is ever found. But there's a problem here: with the Collatz conjecture, given a positive integer $n$, it's not obvious that it's even decidable whether or not $n$ is a counterexample. We can't simply "check whether or not $n$ is a counterexample" like we can with Goldbach's conjecture.

So is there a known Turing machine which halts if and only if the Collatz conjecture is false?

Of course, a "known Turing machine" doesn't have to be a Turing machine that someone has actually explicitly constructed; if it's straightforward how to write a computer program that would do this, then that counts as a "known Turing machine".

On the other hand, saying "it's either the machine which trivially halts, or it's the machine which trivially does not halt" doesn't count as a "known Turing machine"; I'm asking for an answer which mentions one single Turing machine $M$ (with no input or output), such that we know that $M$ halts if and only if the Collatz conjecture is false.

Answer 1

$\newcommand\PA{\mathit{PA}}$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.

Answer 2

See John H. Conway (1972), Unpredicatable Iterations, In: Proc. 1972 Number Theory Conference, University of Colorado, Boulder, CO. 1972, pp. 49–52. (MR 52 #13717).

A summary (item 43 in a paper The $3x + 1$ problem: An annotated bibliography of Lagarias) says, "This paper states the $3x+1$ problem, and shows that a more general function iteration problem similar in form to the $3x + 1$ problem is computationally undecidable."

In fact, it shows that in this family of problems, among which $3x+1$ does not appear to stand out in any way, there are undecidable problems. This doesn't prove that $3x+1$ itself is undecidable, but it's definitely food for thought.