According to http://mathworld.wolfram.com/CollatzProblem.html, the general Collatz problem is undeciadable. For that reason, I'm interested in seeing what it states so that I can get an idea of why it might be undecidable but I can't find a web page that explains what it states in a way I can understand anywhere. Can you give me a clear description of what it states that nonexperts can understand?


The general Collatz problem isn't a problem in the sense of a single question with a yes/no answer; rather, it's a decision problem: we have a bunch of instances, and we want to know which ones satisfy a certain property. Examples of decision problems include:

  • What prime numbers equal $1$ mod $4$?

  • What computer programs eventually halt?

A decision problem is often just thought of as a set, namely the set of instances with the given property.

In the general Collatz problem, the instances are "Collatz-like" functions (or: Collatz-like functions and specific inputs - this was Conway's original formulation), and the property is "every sequence eventually hits $1$." This decision problem is extremely complicated: there is no computer program for determining which instances satisfies the property and which don't.

Now, around the word "undecidable," there's a bit of ambiguity. The word is generally used in one of two ways:

  • A decision problem is undecidable if there is no computer program which "solves" it. In this usage, the generalized Collatz problem is undecidable.

  • A sentence is undecidable from a set of axioms if it can neither be proved nor disproved from those axioms. This is the usage employed when the Wolfram article says "some instances of the generalized Collatz problem are undecidable." Specifically, by the above bullet point we can show: if $T$ is any "reasonable" set of axioms, there will be Collatz-like functions such that $T$ can neither prove nor disprove that they satisfy the property "every sequence eventually hits $1$".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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