Collatz conjecture undecidable from the general case?

Question

There are known results that generalized version of Collatz conjecture is undecidable. I wonder why special case of it still can be decidable? Isn't general case should apply results to all special cases?

Answer 1

We can't decide whether the generalisation is true or false. That means, we can't use any algorithm which would tell us which special cases are true and which are false. However, solving one special case doesn't tell us anything about all the other cases as general. So we might be still able to decide whether a subset of all special cases are true.

Answer 2

Just because a general problem can't be solved, it doesn't follow that specific instances can't be solved. The general fifth-degree polynomial can't be solved by radicals, but certainly there are are particular fifth-degree equations that can be.

A professor once gave me this example of an undecidable problem, each of whose instances is decidable. For each positive integer $n$, let $P(n)$ be the proof in the first order theory of arithmetic with Gödel number $n$. Then the statement, $\exists n, P(n)$ is a proof that $0=1,$ is undecidable. But for any $n$ we can certainly decide it. There is an effective procedure for generating $P(n)$ and then we inspect the last line to see if it says $0=1.$

Answer 3

Isn't general case should apply results to all special cases?

It seems that your confusion stems from this. The phrase "general case" here is used differently from how you are interpreting it. In some situations, "general case" means that it applies to all instances of a problem. In this situations, it means that all problems taken together create an undecidable problem.

The theorem you link states that there exists no terminating Turing machine which can take numbers $P, a_0, b_0, \ldots, a_{P-1}, b_{P-1}$ and output $0$ if the corresponding Collatz conjecture is false, and $1$ if the corresponding Collatz conjecture is true.

The special case here means: is there a Turing machine which can take the (specific) numbers $2, 1/2, 0, 3, 1$ and output $0$ if the ordinary Collatz conjecture is false, or 1 if the ordinary Collatz conjecture is true? The answer is trivially that such a Turing machine exists: either the Turing machine that always outputs 0 will do, or the one that always outputs 1. We just don't know which one it is, yet.