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.