How could the Collatz conjecture possibly be undecidable?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.