Why doesn't the incompleteness theorem answer the decision problem?

Question

The answer (or impossibility of an answer) to Hilbert's Entscheidungsproblem or decision problem is generally attributed to Alan Turing and also independently to Church. My question is why Gödel's proof is not sufficient for showing that not all mathematical problems are decidable? As I understand it Godel showed that first order arithmetic is not complete if it is consistent, and if it is not complete then surely that means it is not decidable? What am I missing?

Answer 1

In a precise sense, it does: we can prove that the halting problem is incomputable directly from (an appropriate formulation of) Godel's incompleteness theorem. However, doing so takes some work, and this work is not needed for Turing's proof.

To even connect the incompleteness of arithmetic with Turing machines, we need to arithmetize Turing machines (in the same way that Godel arithmetized syntax). Moreover, to apply Godel we need to say that (after this arithmetization) the usual Godel sentence can be thought of as a statement about the halting problem. I believe this is basically due to Kleene; the point is that none of this is trivial. In particular, the work taken to arithmetize computability and prove Kleene's result is much harder than just following Turing's proof, which doesn't need any of that. This is why in my opinion it's still fair to attribute the incomputability of the halting problem to Turing (with some combination of Church and Post thrown in for good measure): it only reduces to Godel after it's already understood.

---

That said, here's how we can do that if we want to:

We first bring in the language of the arithmetical hierarchy. Roughly speaking,$^1$ Godel proved that every $\Sigma^0_1$-sound computable set of sentences containing Robinson's $\mathsf{Q}$ is $\Pi^0_1$-incomplete.

Meanwhile, we can prove that there is an appropriate way to talk about Turing machines in the language of arithmetic so that in a precise sense the $\Pi^0_1$ sentences are exactly equivalent to the non-halting claims.

Now consider the theory $$H:=\mathsf{Q}\cup\{"e\in K":e\in K\}\cup\{"e\not\in K": e\not\in K\}$$ (where $K$ denotes the halting problem) gotten by adding to $\mathsf{Q}$ all the "basic halting/non-halting facts."$^2$ (Actually, since $\mathsf{Q}$ is $\Sigma^0_1$-complete we only need to add in the non-halting facts, but meh.) Since $H$ only contains true sentences, $H$ is $\Sigma^0_1$-sound. By the equivalence mentioned above, since $H$ proves all non-halting facts it is also $\Pi^0_1$-complete. So by Godel, $H$ is not computable - and consequently $K$ itself is not computable.

---

$^1$The way I've phrased the incompleteness theorem above is far from optimal. Most interestingly, an improvement by Rosser gets us a stronger result. Namely, Rosser showed that we can replace the hypothesis of $\Sigma^0_1$-soundness by mere consistency in the above version of the incompleteness theorem. Now say that $X$ is "a consistent version of $K$" if the theory $$H_X:=\mathsf{Q}\cup\{"e\in K":e\in X\}\cup\{"e\not\in K": e\not\in X\}$$ is consistent. Applying Kleene as above, we get that $X$ is not computable. So not only is the halting problem itself incomputable, no "consistent version" of the halting problem is computable either.

If you're generally interested in optimizing the incompleteness theorem, see Section $4$ of this paper of Beklemishev.

$^2$ It's crucial that in the definition of $H$ we only threw in the "basic halting/non-halting facts" - e.g. we didn't add any "global" fact like "Every even number is in the halting problem." This is because if we did so, we wouldn't obviously be able to argue that the incomputability of $H$ implies the incomputability of $K$. We need $H$ to be "computably generated" by $K$ for this to work. *(And thinking along these lines will eventually lead to the idea of Turing reducibility, whose introduction kicked off computability theory proper.