How could the Collatz conjecture possibly be undecidable?

I wonder how the Collatz conjecture could possibly be undecidable. Let's say it's undecidable, then no counter example can ever be found, and that to me seems to imply that none exist, and thus that it's true.

• "Undecidability" is a notion relative to a given theory. Feb 19, 2015 at 13:18
• @zarathustra Isn't that independence, not undecidability?
– anon
Feb 19, 2015 at 13:31
• The trouble is that if it can be (and it might be!) undecidable without your knowing it. In this case then as you say it must be true, since any counterexample would decide it, but that's not a contradiction, it only means that its decidability would also be undecidable, and similarly the decidability of its decidability would be undecidable, and so on ad nauseam. Feb 19, 2015 at 13:35
• @SeanEberhard Thanks, the decidability being undecidable makes a lot of sense, and that does seem to avoid this problem. Feb 19, 2015 at 13:38
• @SeanEberhard I am not sure I follow your comments. Are you using the concept of independence or undecidability? If you are speaking of independence, are you saying it's not possible to prove a particular statement is independent of a particular theory? That would be false, for instance Cohen proved CH is independent of ZFC. If you are speaking of decidability, in what sense is determining whether a decision problem is decidable itself a decision problem? What is the input in this 'higher-order' decision problem?
– anon
Feb 19, 2015 at 19:58

The original Collatz problem concerns the $3x+1$ function in particular. The generalized problem takes as input an arbitrary Collatz-like function (a function with associated modulus $n$ that restricts to an affine function $x\mapsto ax+b$, with rational coefficients $a,b\in\Bbb Q$, on each residue class mod $n$) and must determine as output a determination of whether or not the original Collatz problem is resolved in the affirmative for that function. Note a finite amount of data is enough to describe any Collatz function, so this idea makes sense.

It turns out the problem is undecidable: there is no algorithm that can take as input a Collatz-like function and offer as output a yes/no determination of whether every integer iterates to $1$ under the inputted Collatz function. This notion of algorithmic undecidability is to be distinguished from a different notion of independence in mathematical logic. One might claim, for instance, that whether or not the original Collatz conjecture is true, our currect axiom system (the basic assumptions underlying most modern mathematics as encoded in ZFC) is not powerful enough to prove or disprove it. This is for instance what happened with the Continuum Hypothesis: ZFC cannot prove it true or false either way, CH is independent of ZFC.

• Undecidability was proven by John Conway - see Lagarias's survey on the $3x+1$ problem. Feb 19, 2015 at 14:26
• Note, the undecidability of the generalized problem doesn't say anything about the undecidability of the specific one. Mar 18, 2019 at 15:57

Your logic is correct when it comes to non-trivial loops since one of these could be found, and following the cycle would prove its existence.

The trouble comes with sequences which ascend to infinity. It is possible that one could find one, yet be unable to verify that it is one, because one might have to follow it to infinity to prove it - which one can never do.

• "The trouble comes with sequences which ascend to infinity. It is possible that one could find one, yet be unable to verify that it is one, because one might have to follow it to infinity to prove it - which one can never do." That alone makes no sense. The sequence of prime numbers is infinite, yet you can prove that using a finite number of steps. You have no logical basis for why you would have to "follow it to infinity" to prove it.
– name
Sep 29, 2017 at 20:42
• @name that's why I took care to say you might have to follow it to infinity to prove it. If you were able to identify some sequence ascended infinitely without following it all the way, that would not be an example of an undesirable counterexample. But if there is some sequence which ascends to infinity, and the simplest proof that it does so is infinitely long, then the problem is undecidable. Sep 29, 2017 at 21:17
• Perhaps one should include a statement like:"if we don't have an analytical formula to show or disprove that one trajectory is divergent", and enhance more:"if we have a proof, that such a formula cannot exist" Mar 27, 2019 at 8:17

This is not so well known, but Conway came up with a language called Fractran decades ago, but maybe not published at the time of its inception, which is based purely on number theoretic statements and then proved that one can express an undecidable statement in that language.

My understanding (explained to me, havent seen it exactly, hope another knowledgeable expert can better pinpoint it) is that the undecidable statement was shown to have "parallels" to the Collatz conjecture formulation which can be taken as circumstantial evidence that some set of Collatz-like problems are indeed undecidable. have not been able to track down the exact original reference.

The connection between undecidability (connected to/ flip side of Turing Completeness) and number theory is explained by Aaronson in "the enigmatic complexity of number theory" (mathoverflow). this points out Hilberts 10th problem's deep connections to number theory and Turing completeness/ undecidability. In short, no "simple" problems like Collatz are known to be undecidable, but in at least these two cases complex statements written in the "language" of number theory are provably undecidable.

• Fractran's crazy! It might make a good question to see the Collatz algorithm written in Fractran. Oct 1, 2018 at 19:38
• @RobertFrost: I think I've seen that Collatz-algorithm in fractan online some years ago, perhaps you can find it using google/webarchive and the relevant keywords. Oct 2, 2018 at 4:47

In short: There is a small glitch in your reasoning. (See last paragraph of this post if you want to skip the explanation.)

Let's imagine some deity told you that some number n is a counter example. Then you start calculating the sequence and after a day of calculations with your fastest computer, you didn't find the sequence's end. You continue this for a week, a month, a year... and still you didn't find the end of the sequence. You start to believe that the number n is actually a counter example, but you cannot prove it. You can't follow the sequence to an end.
Still there are two possibilities open: 1) there is no end and 2) there is an end, but you didn't follow far enough to reach it. So no matter how long you follow an infinite sequence, these two possibilities will always stay open.

So, there might be counter examples, but then, if it's an undecidable problem, it means that it's impossible to prove the counter examples in one or the other direction.

So the problem is with this sentence: "no counter example can ever be found, and that to me seems to imply that none exist".
That's not true. It might be possible to hold a counter example in your hands. In such a case there is just no way to prove that it is one.

• Remember that to date it is not known if the Collatz conjecture is true or false and it is not known if there can be a proof of it being one of them, i.e. it's decidability is also not known. Sep 23, 2019 at 10:33

It depends on what you mean by truth and falsehood in the first place. Let me explain.

Suppose we’re working inside of some system with axioms and with certain logical rules. We can call a statement $$S$$ to be true if there exists a chain of statements, linked via the rules of deduction, ending in $$S$$. This chain of statements is a proof of $$S$$.

Sometimes, we may be able to find a proof for the statement $$\neg S$$, the negation of $$S$$. In this case, we call $$S$$ false. Under the assumption that we’re dealing with a “sensible” system, no statement can be both true and false.

This leaves a pretty strange possibility. Could a statement exist that is neither true nor false in the aforementioned sense? As it turns out, yes. For example, a particular statement about infinite sets called the Continuum Hypothesis has been shown to be independent of our most common set of axioms. That is, a proof of the Continuum Hypothesis can’t be constructed, and neither can a disproof. Some [citation needed] even suspect that the Collatz Conjecture might fall into this category of undecidable statements.

But here’s the catch: How do you prove a statement is undecidable? The short answer is: you really don’t.

When we talk about decidability, we’re no longer talking about mathematics, not in the regular sense. You can’t construct a proof about the nonexistence of a proof. But you can use the ordinary laws of deduction to talk about mathematical theories themselves, in what we might call meta-mathematics. For example, regarding the Continuum Hypothesis, it was proven that both adding it to our set of axioms and adding its negation produced theories that were just as valid. The argument is precise and solid – don’t get me wrong, this result is established. But it lies in the mathematical metatheory, and not in the theory itself.

What does all of this have to do with Collatz? Well, your argument proves that if the Collatz Conjecture were undecidable, it would have to be true (in the intuitive sense). But this wouldn’t constitute a proof: a proof needs to be contained in the theory, and our argument lies on the metatheory. So, Collatz could pretty well be undecidable, which would make all of our search attempts futile, while proving nothing.

If this still isn’t clear, we can try another example of a very similar nature. Ever wonder why the induction needs to be taken as an axiom in some systems? (Notably in the Peano Axioms). If we had some statement $$P(n)$$ depending on a natural number $$n$$, and knew $$P(0)$$, and that for all $$k$$, $$P(k)\Rightarrow P(k+1)$$, we could prove $$P(n)$$ for any $$n$$. For example, to prove $$P(5)$$, $$P(0)\Rightarrow P(1)\Rightarrow P(2)\Rightarrow P(3)\Rightarrow P(4)\Rightarrow P(5).$$ In an analogous manner, with enough time (and patience), I could write a proof for $$P(10)$$, $$P(1000)$$, or $$P\left(10^{10^{100}}\right)$$. And yet, I would be unable to prove $$P(n)$$ for all $$n$$, since my algorithm to construct a proof belongs to the metatheory, and not the theory itself, of natural numbers.

I hope all of this makes your issue clearer.