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.

  • 15
    Put another way, you are asking whether the Collatz conjecture has a known $\Pi^0_1$ equivalent. As far as I'm aware, the answer is no. – Noah Schweber Aug 24 at 18:36
  • 4
    Your question is basically a duplicate of the following question on Math StackExchange: math.stackexchange.com/questions/100218/… – Timothy Chow Aug 24 at 18:39
  • 7
    YES. (1) there is a Turing machine that never halts (2) there is a Turing machine that always halts One of those is your answer. Now, try to phrase your question so that my answer no longer applies. – Gerald Edgar Aug 24 at 19:10
  • 4
    @ToddTrimble Gerald Edgar's answer probably better fitted as a comment, and possibly relies on a misunderstanding, but I believe deleting it as spam overrides the moderator's role. – YCor Aug 24 at 20:11
  • 4
    So in any case, the conjecture is equivalent to the halting of a "known" program. The actual question should be: is the Collatz conjecture provably equivalent (in PA?) to the halting of a particular program? – Joel David Hamkins Aug 24 at 22:03
up vote 11 down vote accepted

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 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.

  • 4
    Let me point out that a certain generalization of the Collatz problem is also proven to be $\Pi_2^0$-complete in this paper. – Burak Aug 24 at 22:24
  • Related (and gives at least a suggestive picture of the relationship of 3x+1 to universal computation): cstheory.stackexchange.com/a/11614/129 – Joshua Grochow Sep 15 at 11:25

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.

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.