How can you prove Gödel's incompleteness theorem from the halting problem? Is it really possible to prove the full theorem? If so, what are the differences between original proof and proof by halting problem?

  • 5
    $\begingroup$ You'll probably enjoy reading this recent blog post by Scott Aaronson. $\endgroup$ – t.b. Jul 23 '11 at 15:24
  • $\begingroup$ For a formal self-contained version of the proof given in the linked blog post, see this post. It shows exactly where Godel's coding trick is needed. Also, see this article for why the coding trick is needed for PA only because it is too weak to natively reason about string manipulation. $\endgroup$ – user21820 Feb 25 '17 at 7:05

A somewhat subtle point in the proof that Zhen Lin sketched in another answer is that it has to assume that Peano arithmetic is $\omega$-consistent. This is because the algorithm sketched looks for a proof of "there exists a number of steps after which $M$ halts", but if Peano arithmetic was not $\omega$-consistent then it might prove a statement of that kind without such a number actually existing. This extra assumption of $\omega$-consistency is typical of computability-theoretic proofs of the incompleteness theorem.

I don't know of any proof of the full incompleteness theorem (the one that assumes only consistency) just from the unsolvability of the halting problem, and I doubt such a proof exists for two reasons.

First, the unsolvability of the halting problem is a fact at the meta level (a fact about the standard model). If you look at some theory of arithmetic that is consistent but not satisfied by the standard model, it could prove all sorts of false statements about whether various Turing machines halt. The assumption of $\omega$-consistency is exactly intended to give a link between the meta level and the object level of the theory at hand. Without such an assumption, the two can be very different.

Second, there are (non-effective) completions of Peano arithmetic that do not solve the halting problem, and are of strictly lower Turing degree while still being uncomputable. In other words, formally, the Medvedev degree of the set of completions of PA is strictly weaker than the Medvedev degree of the set of oracles that compute the Halting problem. My interpretation of this result is that it's a steep obstacle to proving the full incompleteness theorem using just computability-theoretic methods, because it means we can't just reduce the completion problem to the halting problem as is normally done in computability.

Part 2

Now I want to write about the blog post that you can find here which was linked in the comments. The method in that post uses a different unsolvable problem, namely the problem of finding a separating set for a certain pair of recursively inseparable r.e. sets. These sets are the set of machines which PA can prove to halt, and the set of machines which PA can prove to not halt. In the blog post, this separating set is a solution to the "Consistent Guessing Problem".

The Turing degrees that are able to compute such sets are known as PA degrees (Wikipedia article) because they are also the degrees that are able to compute a completion of Peano arithmetic. There is a little more info on these degrees in the Wikipedia article.

| cite | improve this answer | |
  • $\begingroup$ The blog post mentioned in Part 2 makes it sound like the argument is purely computability-theoretic and doesn't assume omega-consistency. Is it not? $\endgroup$ – arsmath Jan 17 '13 at 11:52
  • $\begingroup$ @arsmath: the proof in the blog only assumes consistency, not $\omega$-consistency. But instead of using the halting problem, it uses a different sort of problem, which is to find a separating set for a pair of disjoint r.e. sets. This is a different sort of problem because it is a mass problem rather than a decision problem. The argument I wanted to describe here is that I don't know of a proof of the incompleteness theorem that works by reducing the completeness problem to a single decision problem. $\endgroup$ – Carl Mummert Jan 17 '13 at 12:22
  • $\begingroup$ Separately, my description in Part 2 isn't right. The sets should be: the set of machine which PA proves to halt and return 0, and the set of machines which PA proves to halt and return 1. $\endgroup$ – Carl Mummert Jan 17 '13 at 12:23
  • $\begingroup$ Thank God. I had one of those "Oh my God, I'm losing my mind and I understand nothing" moments. The distinction you're making makes perfect sense, now that I understand it. $\endgroup$ – arsmath Jan 17 '13 at 12:30

We will assume Peano Arithmetic is consistent throughout. Suppose Gödel's first incompleteness theorem is false; that is, assume for every well-formed sentence $P$ in the language of Peano Arithmetic, either $P$ is provable or $\lnot P$ is provable. Then we may solve the halting problem: consider a Turing machine which accepts an encoded Turing machine $M$ as input, forms the sentence $P$ in Peano Arithmetic which asserts that $M$ halts on all inputs, and searches for a proof of $P$ or $\lnot P$ by iterating through all possible proofs, halting when such a proof is found. This Turing machine is guaranteed to halt by our assumption, so we have indeed solved the halting problem. But the halting problem cannot be solved, so Gödel's first incompleteness theorem must be true.

Note: Carl Mummert's answer elaborates on the consistency assumption required here.

| cite | improve this answer | |
  • $\begingroup$ So the original proof of incompleteness doesn't assume Peano Arithmetic is consistent? Is that the only assumption use by your proof? What is the major difference between original and this one? $\endgroup$ – Mark Jul 23 '11 at 15:33
  • $\begingroup$ And is this suppose to prove the whole statement of incompleteness? $\endgroup$ – Mark Jul 23 '11 at 15:41
  • $\begingroup$ The original proof of incompleteness assumes consistency, of course. Otherwise any statement is already provable. $\endgroup$ – Zhen Lin Jul 23 '11 at 15:50
  • $\begingroup$ So it assumes Peano Arithmetic? $\endgroup$ – Mark Jul 23 '11 at 15:56
  • $\begingroup$ Strictly speaking, I believe it does not assume the ω-consistency of Peano Arithmetic. Gödel's original proof was for the logical system of Principia Mathematica and assumes the ω-consistency of that theory. $\endgroup$ – Zhen Lin Jul 23 '11 at 16:03

Here is a reference http://www.logicmatters.net/resources/pdfs/PartIII.pdf discussing both methods (Gödels method and the proof using the halting problem)

Scott Aaronson made a wonderful post about this (and an even stronger result) on his blog: http://www.scottaaronson.com/blog/?p=710

| cite | improve this answer | |

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.