# 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:** 1\
**Showing post:** 8

<div class="post-metadata">

**Author:** ![hoenikker](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hoenikker/32/7296_2.png) [@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")

</div>

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)

---

_[View the full topic](https://boards.straightdope.com/t/godels-incompleteness-theorem-and-the-halting-problem/597077)._