# Gödel's incompleteness theorem and the halting problem
**URL:** https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077
**Category:** Factual Questions
**Created:** [September 21, 2011, 4:14pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077 "2011-09-21T16:14:33Z")
**Posts on this page:** 17
**Page:** 1
### Author:  [@hoenikker](https://boards.straightdope.com/u/hoenikker)
#### Post date: [September 21, 2011, 4:14pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/1 "2011-09-21T16:14:33Z")
What’s the relationship between Gödel incompleteness and the halting problem? Is either a stricter version of the other? And if not, is it possible that both are a stricter version of a more general principle that applies to a wider class of systems than either formal models of arithmetic and TM’s?
I ask because, from my limited understanding, it seems they must be related in some way, but I’ve read posts in this [much earlier thread](http://boards.straightdope.com/sdmb/showthread.php?t=176707) that suggest otherwise. Consider, for example, [Goldbach’s conjecture](http://en.wikipedia.org/wiki/Goldbach's_conjecture), which some suggest might be a true but unprovable statement, the possibility of which is guaranteed by Gödel’s. However, it’s easy to create a Turing machine that halts iff Goldbach’s conjecture is false: just go through all integers one by one and halt if you find a counterexample. If Goldbach’s is true and unprovable though, then it must be that this is a TM that halts but cannot be proven to halt, the possibility of which is guaranteed by the halting problem. So it seems like the two ideas must be linked…
Also, to throw another spanner in the works, what about Turing oracles? If a first-order Turing oracle existed (solving the halting problem on TMs, but not its own halting problem), then it could clearly prove or disprove Goldbach’s. So does “unprovable” in Gödel’s really mean unprovable in finite time?
Thanks in advance for any insight!!
---
### Author:  [@Reno\_Nevada](https://boards.straightdope.com/u/Reno_Nevada)
#### Post date: [September 21, 2011, 4:47pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/2 "2011-09-21T16:47:04Z")
I am not a mathematician but I am a computer scientist, so I can speak with marginal authority on this. As far as I know, the Incompleteness Theorem and the Halting Theorem are not directly related, in that they were proved by different people using different approaches. Neither can really be considered a subset of the other.
On the other hand, they are similar, in that they refer to formal systems that can represent themselves recursively, and there is probably a general statement that could incorporate both of them.
By the way, it is trivial to create a Turing machine that halts. First instruction–halt. Done! The problem is to determine if a random Turing machine would halt with any input.
An excellent book on this subject, as well as many others, is \*Godel Escher Bach: An Eternal Golden Braid \*by Douglas Hofstadter. It is not easy going but it is very rewarding.
---
### Author:  [@hoenikker](https://boards.straightdope.com/u/hoenikker)
#### Post date: [September 21, 2011, 5:03pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/3 "2011-09-21T17:03:05Z")
> [@Reno\_Nevada](#):
>
> On the other hand, they are similar, in that they refer to formal systems that can represent themselves recursively, and there is probably a general statement that could incorporate both of them.
Cool, that’s exactly what I’m getting at…is there any research into what kind of statement that might be?
> [@Reno\_Nevada](#):
>
> By the way, it is trivial to create a Turing machine that halts. First instruction–halt. Done! The problem is to determine if a random Turing machine would halt with any input.
Yep, of course, but such a trivial machine can be proved to halt with a finite length proof. If Goldbach’s is true but unprovable, then presumably no finite length proof will show whether the TM described in the OP will halt or not. However, a Turing oracle would. Is this true in general? Can all true but unprovable statements be proved with a Turing oracle?
---
### Author:  [@hoenikker](https://boards.straightdope.com/u/hoenikker)
#### Post date: [September 21, 2011, 5:11pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/4 "2011-09-21T17:11:03Z")
Actually, scratch that last part. Obviously, not all true by unprovable statments will be provable with a Turing oracle that solves the (first-order) halting problem. But regardless, I’d be interested if such a Turing oracle corresponds to any concept related to Gödel’s incompleteness…
---
### Author:  [@Chronos](https://boards.straightdope.com/u/Chronos)
#### Post date: [September 21, 2011, 5:18pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/5 "2011-09-21T17:18:40Z")
**Indistinguishable** will be along soon enough, I’m sure, but from what I remember from previous threads, both Turing’s and Gödel’s theorems, as well as Cantor’s proof of the uncountability of the reals, are special cases of a more general theorem that can apply to a very wide variety of different contexts.
And there’s a hierarchy of unresolved problems based on what sort of oracle would solve them. Many interesting problems would be solved by a first-order oracle that can solve the Halting Problem for Turing machines. Then you could have a second-order oracle, that can solve the Halting Problem on a system of Turing machine plus first-order oracle, and higher-order oracles according to the same pattern. IIRC, the Twin Prime Conjecture would (so far as anyone can tell) require a second-order oracle to resolve it, though I don’t know of any problems offhand that would require a third-order oracle (they doubtless exist, though).
---
### Author:  [@hoenikker](https://boards.straightdope.com/u/hoenikker)
#### Post date: [September 21, 2011, 5:27pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/6 "2011-09-21T17:27:59Z")
> [@Chronos](#):
>
> **Indistinguishable** will be along soon enough, I’m sure, but from what I remember from previous threads, both Turing’s and Gödel’s theorems, as well as Cantor’s proof of the uncountability of the reals, are special cases of a more general theorem that can apply to a very wide variety of different contexts.
Great, that’s exactly what I was hoping to find out about.
---
### Author:  [@Bytegeist](https://boards.straightdope.com/u/Bytegeist)
#### Post date: [September 21, 2011, 6:05pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/7 "2011-09-21T18:05:46Z")
There’s an earlier (and long) thread on the subject [here](http://boards.straightdope.com/sdmb/showthread.php?t=543130).
---
### Author:  [@hoenikker](https://boards.straightdope.com/u/hoenikker)
#### Post date: [September 21, 2011, 7:34pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/8 "2011-09-21T19:34:55Z")
Ahh, ok, thanks **Bytegeist**. Unfortunately that thread is similar to the one that I linked to in my OP, in descending into a heated debate…
Anyway, I gather from reading that thread that statements which are neither provable nor disprovable within a system are (usually/always?) due to them implicitly encoding some form of self-reference within them, and that Gödel’s in particular shows that, in the case of any system obeying the axioms of Peano arithmetic, and that they may be very well hidden as apparently simple statements of pure arithmetic.
> [@Godel: are all undecidable props in consistent math systems subsets of self-referent statements?](https://boards.straightdope.com/t/godel-are-all-undecidable-props-in-consistent-math-systems-subsets-of-self-referent-statements/520559/12):
>
> Goedel’s theorem is not even fundamentally about just computable theories [as seen by its alter ego, Tarski’s indefinability theorem]. (For that matter, I daresay the near-universal presentation of GIT1 in terms of incompleteness is an accident of history, setting an odd focus. But I digress). For example, it tells us that an axiomatization of true arithmetic (all the true first-order statements in the language of PA) cannot even be given by a program equipped with an oracle for the halting problem + an oracle for the halting problem for machines equipped with an oracle for the halting problem + an oracle for … .[sup]1[/sup] This, of course, goes well beyond plain computability.
Ok, this is really interesting. I’m just going out on a limb here (and please excuse my sloppy language), but would it make sense to say that every level of Turing oracle-ness peels away another “layer” of problems from the space of all problems, making them computable, like peeling all layers of some (very transfinite) onion. As you add more and more layers of oracle-ness, you will be able to compute the answers to more and more problems, however, but the set of problems which you cannot solve will approach some steady set?
If that’s the case, then what would this final set of problems that you cannot solve look like? Would they all be very trivial forms of self reference? Basically, would an infinite-order Turing oracle be able to solve anything that wasn’t a “clear” (for some definition of clear) paradox (similar to the problem of asking God to create a rock so heavy that even He could not lift it, to throw in a metaphor)
---
### Author:  [@ZenBeam](https://boards.straightdope.com/u/ZenBeam)
#### Post date: [September 21, 2011, 9:53pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/9 "2011-09-21T21:53:37Z")
> [@hoenikker](#):
>
> Basically, would an infinite-order Turing oracle be able to solve anything that wasn’t a “clear” (for some definition of clear) paradox (similar to the problem of asking God to create a rock so heavy that even He could not lift it, to throw in a metaphor)
Just a baseless hunch, but if you assumed a _countably_ infinite Turing machine, someone would probably come up with a problem requiring an _uncountably_ infinite Turing machine (whatever that is).
(Actually, my hunch is that both of those have already occurred.)
---
### Author:  [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)
#### Post date: [September 21, 2011, 10:06pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/10 "2011-09-21T22:06:52Z")
> [@Reno\_Nevada](#):
>
> I am not a mathematician but I am a computer scientist, so I can speak with marginal authority on this. As far as I know, the Incompleteness Theorem and the Halting Theorem are not directly related, in that they were proved by different people using different approaches. Neither can really be considered a subset of the other.
Actually, the Halting Problem and the Incompleteness Theorem are pretty closely related. The basic outlines of their proofs are very similar essentially using the same diagonalisation trick, and the Halting Problem can be viewed as a theorem that, though it appeared in the literature later, is actually a conceptual predecessor of the Incompleteness Theorem. Indeed, if you have the notion of Turing Machine handy, as well as a proof of the Halting Problem, a strengthening of the Incompleteness Theorem in the form of [Rosser’s Theorem falls out as a corollary](http://www.scottaaronson.com/blog/?p=710).
---
### Author:  [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)
#### Post date: [September 21, 2011, 11:46pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/11 "2011-09-21T23:46:45Z")
Capt. Ridley is absolutely correct. For one thing if the halting problem for a machine is undecidable, then so is the conjecture that it halts. And that can be coded in Goedel arithmetic. I’m pretty sure you can go the other way too, code an arithmetic statement into a halting problem. And they certainly have the same “feel”.
---
### Author:  [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)
#### Post date: [September 22, 2011, 12:35am UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/12 "2011-09-22T00:35:19Z")
> [@Capt.Ridley\_s\_Shooting\_Party](#):
>
> Actually, the Halting Problem and the Incompleteness Theorem are pretty closely related. The basic outlines of their proofs are very similar essentially using the same diagonalisation trick, and the Halting Problem can be viewed as a theorem that, though it appeared in the literature later, is actually a conceptual predecessor of the Incompleteness Theorem. Indeed, if you have the notion of Turing Machine handy, as well as a proof of the Halting Problem, a strengthening of the Incompleteness Theorem in the form of [Rosser’s Theorem falls out as a corollary](http://www.scottaaronson.com/blog/?p=710).
This is borne out in Michael Sipser’s book on computation theory, where he derives the incompleteness theorem pretty easily from the basic notions of uncomputability. But just out of curiosity, is there any insight to be gained by looking at the two statements in light of Curry-Howard?
---
### Author:  [@hoenikker](https://boards.straightdope.com/u/hoenikker)
#### Post date: [September 22, 2011, 1:34am UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/13 "2011-09-22T01:34:43Z")
> [@ultrafilter](#):
>
> This is borne out in Michael Sipser’s book on computation theory, where he derives the incompleteness theorem pretty easily from the basic notions of uncomputability.
That’s great, and confirms my initial intuition that the two are related. But according to **Indistinguishable** , Gödel’s goes further than simple uncomputability and implies that statements exist that can’t be proved or disproved by any level of Turing oracle-ness. Anyone have any idea what kind of statement that would be?
Also, I’ve seen mentioned the idea of Gödel sentences, but I don’t really understand quite what they are. Would a Gödel sentence for a particular system be encodable as a particular TM, or does that not make sense?
---
### Author:  [@Chronos](https://boards.straightdope.com/u/Chronos)
#### Post date: [September 22, 2011, 5:52am UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/14 "2011-09-22T05:52:40Z")
A Gödel sentence is a sentence constructed in some logical system which cannot be proven nor disproven within that logical system.
---
### Author:  [@Half\_Man\_Half\_Wit](https://boards.straightdope.com/u/Half_Man_Half_Wit)
#### Post date: [September 22, 2011, 7:23am UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/15 "2011-09-22T07:23:18Z")
> [@hoenikker](#):
>
> Cool, that’s exactly what I’m getting at…is there any research into what kind of statement that might be?
There’s a fixed-point theorem originally due to Lawvere that incorporates basically all the classical paradoxes of self-reference – it’s discussed and explained in this [pedagogical paper](http://arxiv.org/abs/math/0305282).
I think it’s also useful to refer to the work of Chaitin, who showed that the halting probability of a Turing machine, and uncomputable number, can by any given formal system only be approximated to a finite degree – i.e. after some certain bit in the binary expansion of the halting probability, the value of any following bit isn’t derivable. This is a statement of the incompleteness theorem, and it follows directly from the fact that if you could derive all the values of all the bits of the halting probability, you could also solve the halting problem. ([See here](http://en.wikipedia.org/wiki/Chaitin%27s_constant) for an overview.)
---
### Author:  [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)
#### Post date: [September 22, 2011, 8:30am UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/16 "2011-09-22T08:30:43Z")
> [@ultrafilter](#):
>
> But just out of curiosity, is there any insight to be gained by looking at the two statements in light of Curry-Howard?
Not that I’m aware, or at least I don’t see any deep rephrasing of the two subjects in those terms. Curry-Howard discusses the analogy between typed lambda-calculi and intuitionistic logics (and player-opponent games, and categories, and …). The typed lambda-calculi in question almost always are strongly normalizing (in fact, I’d argue for there to be any interest in the correspondence they _must_ be at least weak head normalizing), and therefore there’s no corresponding halting problem.
---
### Author:  [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)
#### Post date: [September 22, 2011, 7:04pm UTC](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077/17 "2011-09-22T19:04:43Z")
> [@hoenikker](#):
>
> Also, I’ve seen mentioned the idea of Gödel sentences, but I don’t really understand quite what they are. Would a Gödel sentence for a particular system be encodable as a particular TM, or does that not make sense?
The book recommended above, _GEB_ does a good job of showing you how to construct a Godel sentence.
Essentially, the process he goes through (as far as I remember) is:
1. Using several simpler languages as building blocks, he constructs a language in which you can make statements about number theory (ie, “three is a prime number”, “there are no a,b,c,n \>2 for which a^n + b^n = c^n”, “2 \> 7”), which can be either true or false, using a fairly restrictive set of symbols.
2. He establishes a set of typographical rules and axioms for generating theorems in this language, ie, sentences that are true, without ascribing meaning to the manipulation. That is, you can take one or more true statements and generate new ones without
3. He encodes the symbols used in the language in step one into numerical form.
4. He demonstrates that the typographical rules derived in step 2 are actually mathematical rules; the combination of some string(s) symbols to create another string of symbols, when encoded as numbers, is basically shifting (multiplying by a factor of 10^n) and addition, which are mathematical operations that the language itself can describe.
5. He constructs a sentence (in number form), that, when translated back to the symbols, is a statement about the number form of that sentence, and which includes a contradiction. Since this sentence can be neither true nor false within the context of the given system, the system is incomplete.
Note that the Godel sentence is the sentence that proves Godel’s theorem. It’s not necessarily the only way to make a statement within a given system that can neither be proven nor disproven.