31

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.

RobPratt
  • 5,169
Tanner Swett
  • 1,133
  • Why can’t you check all numbers up to $n$ and see whether they fall into a bad cycle before the $n$th step? – Anthony Quas Aug 24 '18 at 18:08
  • 1
    @AnthonyQuas Because the Collatz conjecture may have counterexamples where the hailstone sequence doesn't fall into a bad cycle (it may increase without bound instead). – Tanner Swett Aug 24 '18 at 18:11
  • Oh yes. I forgot about that possibility. – Anthony Quas Aug 24 '18 at 18:13
  • 21
    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 '18 at 18:36
  • 4
    Your question is basically a duplicate of the following question on Math StackExchange: https://math.stackexchange.com/questions/100218/is-the-collatz-conjecture-in-sigma-1-pi-1 – Timothy Chow Aug 24 '18 at 18:39
  • 3
    There was a answer by Gerald Elgar, which should rather have been a comment, and deleted by a moderator as spam (!!!!), which from my (probably incorrect) understanding was technically correct, namely "if CC holds, the machine that returns no, if CC fails, the machine that returns yes". So I'd like to understand why this does not answer the question (the comment "you drew the parentheses wrong, not him" by Gerhard Paseman doesn't help me). Could it be clearly asserted what is the desired input and output of a machine as in the question? – YCor Aug 24 '18 at 20:08
  • 6
    @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 '18 at 20:11
  • @YCor I edited my question to hopefully clarify that. 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. – Tanner Swett Aug 24 '18 at 20:12
  • @YCor: Whether Gerald's answer was technically correct depends on your interpretation of the question. If the OP is interpreted as asking for a Turing machine T for which we currently have a proof of the equivalence "T halts iff CC fails" in some base system such as ZFC or PA, then Gerald's answer was not correct. If it is interpreted as asking for the existence of a Turing machine T for which it holds in the set-theoretic universe that "T halts iff CC fails", then his answer was technically correct. I believe the suitable phrasing of the question should be as in the MSE post linked above. – Burak Aug 24 '18 at 20:12
  • Of course, if the Collatz conjecture is ever proved or disproved, then the answer that Gerald wrote will be correct! – Tanner Swett Aug 24 '18 at 20:14
  • 12
    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 '18 at 19:10
  • 3
    @YCor I didn't delete "as spam", but acted on a flag. I didn't mean to do so inappropriately; it's now a comment. – Todd Trimble Aug 24 '18 at 20:19
  • The suggested grouping starts with a main clause :" Is there machine T such that (T halts iff Collatz)". Gerald's answer suggests (is there T that halts) iff (Collatz). I don't mind the regrouping so much as the implicit attitude. If Gerald had suggested a clarification rather than issue a challenge, my comment would have been different. I would not call his answer spam. Neither would I call it helpful nor would I call it appropriate to the mission of the forum. Gerhard "Usually I Respect Gerald's Posts" Paseman, 2018.08.24. – Gerhard Paseman Aug 24 '18 at 20:20
  • 1
    Sounds like a matter of the order of quantifiers: I meant to ask "does there exists T such that (it is known that (T halts iff not Collatz))", and Gerald answered "is it known that (there exists T such that (T halts iff not Collatz))". In any case, I think my question and the linked MSE question are slightly different. The MSE question asks "is Collatz equivalent to either a $\Sigma_1$ statement or a $\Pi_1$" statement"; I'm asking "is Collatz equivalent to a known $\Pi_1$ statement". – Tanner Swett Aug 24 '18 at 20:29
  • The answer definitely seems to be "no, no such Turing machine is known", but it'll be hard to produce an authoritative answer based on that... – Tanner Swett Aug 24 '18 at 20:30
  • 1
    @TannerSwett I'm skeptical about the use of "it is known that" in a logical statement. What is somebody in a cave has a working proof that Collatz holds? – YCor Aug 24 '18 at 20:35
  • 2
    @YCor furthermore, we need to worry about whether the interior and exterior of a cave are well-defined notions. – PrimeRibeyeDeal Aug 24 '18 at 20:40
  • 3
    The question suffers from a uniformity issue common to many similar questions. Namely, the answer is yes, because: if the Collatz conjecture is true, then it is equivalent to the halting of the Turing machine program that halts immediately, and this program is "known"; and if the Collatz conjecture is false, then it is equivalent to the halting of the program that never halts, and such a program is "known." – Joel David Hamkins Aug 24 '18 at 22:03
  • 5
    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 '18 at 22:03
  • 4
    But I see that this comment is also the content of the answer posted by Gerald Edgar, and apparently deleted by a moderator. But I don't think it should have been deleted, since I think there is a kind of sloppiness in the question, which is quite a common kind of sloppiness that infects many questions of beginners in complexity theory. The question is not sensible unless one specifies a specific theory and asks for a proof of equivalence to a $\Pi^0_1$ statement. – Joel David Hamkins Aug 24 '18 at 22:07
  • 4
    For example, one can find many people asking such things as: is there a Turing machine that correctly states whether or not the continuum hypothesis is true? (And this is essentially the same as the current question, but with CH instead of CC.) The answer is yes, as Gerald indicated, because there are machines that say "yes" and machines that say "no", and one of these is correct. It is no good to reject this answer is "not what I meant"; rather, one must actually ask the question that is meant, and this will be a bit subtler and will require one to think harder about foundational matters. – Joel David Hamkins Aug 24 '18 at 22:15
  • @Joel, indeed, and the poster attempted to explain the question more precisely with the examples. Is there a way of phrasing it better to reveal these issues? Given the care you usually give to your posts, I imagine you have read what was posted. However, it seems from the comments that you and Gerald are responding only to the title (which could be improved, but only marginally) and not the post. Gerhard "Say It Isn't So Joel" Paseman, 2018.08.24. – Gerhard Paseman Aug 24 '18 at 22:39
  • 3
    If everyone would please take note: the "answer" by Gerald Edgar was not an answer, but a comment: a "request" to clarify the question. (It was also flagged as rude/abusive, which partly explains the initial action of deletion.) It now appears as a comment, intact, above, where it belongs. Everyone can see it and act accordingly. (I am also being accused of overstepping my bounds, replete with a rash of exclamation points, whereas from my POV I'm just trying to carry out my duties in attending to flags. I'd like to request that people withhold accusations, and stick to math. Thank you.) – Todd Trimble Aug 24 '18 at 23:00
  • @TannerSwett : Your intended question is the same as the intended question in the linked MSE question. If you read the text of the MSE question, it says, "is Collatz known to be equivalent to a $\Sigma_1$ or $\Pi_1$ statement?" By the way, your suggested formulation "is Collatz equivalent to a known $\Pi_1$ statement" is also unacceptable to a pedant, because what you are hoping is known is the equivalence and not the statement. It does you no good to know a statement if you don't know that it's equivalent to Collatz. – Timothy Chow Aug 25 '18 at 00:51
  • 2
    Gerhard, yes, I saw the edit in the question, but it still doesn't mention any theory, which I find to be the crux of the foundational confusions here, and also, the "always halt" program is one specific program, as is the "never halt" program. Also, if one is just asking for an equivalence, then the question trivializes, since all true statements are equivalent. Rather, what I find to be at issue is whether the equivalence can be proved in a specific theory, such as PA. This is a bit closer to what Timothy's pedant is getting at, but even he doesn't mention the role of the theory. – Joel David Hamkins Aug 25 '18 at 01:41
  • 2
    Meanwhile, I don't find the issue pedantic, since as I mentioned, this is unfortunately a very common mistake which leads to many confusions, and I find it important to get it right. I view it as fundamentally similar to the kind of mistake that beginners make in complexity theory by asking about the complexity of a problem, but being vague about what the problem is exactly, for example, by not specifying the exact input/output. – Joel David Hamkins Aug 25 '18 at 01:45
  • @JoelDavidHamkins Well, I'm not asking whether or not the equivalence can be proved in any one theory; I'm asking whether or not we humans already know of "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" (quoting from my question). To me, it the question seems clear as to what I'm asking; is there something else I could add or change to make it clearer? – Tanner Swett Aug 25 '18 at 15:07
  • 1
    Yes, I had seen what you wrote. The "always halt" program is one single program, and we already know of it. And the "never halt" program is one single program, and we already know of it. And depending on whether the Collatz conjecture is true or false, therefore, exactly one of these is a single program, that we already know of, which halts iff CC is false. If you object to this by saying we don't know the final equivalence, then I would ask, what does it mean to know an equivalence like this, except to have a proof in a certain theory? But you haven't mentioned any theory. – Joel David Hamkins Aug 25 '18 at 15:25
  • 1
    Perhaps this answer and discussion help explain the point I am trying to make: https://mathoverflow.net/a/48031/1946. – Joel David Hamkins Aug 25 '18 at 15:26
  • 2
    It may also be helpful to consider also the program that searches for a proof (in ZFC, say, or whatever your favorite strong theory is) that CC is false. We can easily design such a program. It follows that this particular program halts if and ony if there is provably a counterexample to CC. If it turns out that CC is independent of the theory, then it becomes a philosophical question as to whether it is true or not. – Joel David Hamkins Aug 25 '18 at 16:49
  • @TannerSwett: Let me explain the issue with a concrete example. It is a theorem of ZFC that every Goodstein sequence terminates (let's call this statement GS.) Therefore, in ZFC, we have the equivalence "GS iff T halts" where T is the Turing machine which halts after a single step on any input. Now, it is also known that GS is not a theorem of PA. Therefore, the equivalence "GS iff T halts" cannot be proven in PA. As you can see, one theory is able to prove the equivalence whereas the other is not. This is exactly Joel's point made above. – Burak Aug 25 '18 at 17:25
  • @TannerSwett: This is why the base theory matters. Here is a correct formulations of your question: Has someone explicitly constructed a Turing machine T for which we have that the equivalence "CC iff T does not halt" is proven in (your favorite base theory that is able to talk about Turing machines)? Since we do not know whether CC is true or not at the moment, the answer that T is the machine that always halts or never halts is not meaningful. (However, once CC is proven or disproven, we will know which equivalence can be proven.) – Burak Aug 25 '18 at 17:30
  • @JoelDavidHamkins I understand very well how statements like "the life-on-Mars language is computable" and "the Collatz conjecture is equivalent to some Turing machine" are true; I don't have any misconceptions there that need clearing up. I don't quite disagree that my question only makes sense in the context of a particular theory... but I don't understand why you're asking "what theory?" for this particular question. If I had asked "is it known whether or not such-and-such Diophantine equation has any solutions", would you still have asked "known in which theory"? – Tanner Swett Aug 26 '18 at 00:27
  • @TannerSwett: Please read my comment regarding termination of Goodstein sequences. The answer to your last question is YES. You can write down a Diophantine equation whose solution exists if and only if PA is inconsistent. In this case, PA would not be able to detect the non-existence of solutions whereas ZFC would. Another example this polynomial which can be proven to not have a solution in integers in ZFC+Inaccessible but you cannot do this in ZFC. In any case, even if you set your background theory to be ZFC in the OP, I believe the current answer is NO. – Burak Aug 26 '18 at 12:46
  • 1
    @TannerSwett: Maybe this example will clear things up for you. Consider the Turing machine $T_1$ which looks for a counterexample of, say, Goldbach's conjecture after searching and finding a proof of 0=1 in PA, and the Turing machine $T_2$ which just looks for a counterexample of Goldbach's conjecture directly. Do you think it makes sense to ask "Do we know the equivalence $T_1$ halts iff $T_2$ halts?" without specifying a base theory? – Burak Aug 26 '18 at 12:53

2 Answers2

29

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

LSpice
  • 11,423
Bjørn Kjos-Hanssen
  • 24,629
16

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.

LSpice
  • 11,423
Gerry Myerson
  • 39,024