Timeline for What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 13, 2023 at 19:19 | comment | added | C7X | @jvdh It's not finite, but countable. If $\mathsf{PA}$ is the set of proofs, and $\pi:\mathbb N\to\mathsf{PA}$ is an enumeration of them, then we can check the proofs $\pi(n)$ in order. Under the contradiction assumption that PA is complete, $\sigma$ or $\lnot\sigma$ is one of the $\pi(n)$ for finite $n$, and at that point we stop since we have solved the halting problem for $M$. | |
| May 23, 2020 at 12:31 | comment | added | jvdh | How do we know that the set of all proofs in PA (or T) is finite? If it is infinite, we could not solve the halting problem by going through all proofs in PA (or T). | |
| Oct 2, 2018 at 7:47 | comment | added | Ingo Blechschmidt | (continued) For this, let $M$ be the machine which searches all $T$-proofs for a proof of "$M$ halts" or "$M$ doesn't halt" and, upon finding such a proof, performs the opposite of what the proof is claiming. Assume that $T$ proves that $M$ halts or that $T$ proves that $M$ doesn't halt. Looking at the first-found proof of either statement, we can then deduce with some work that $T$ is inconsistent. | |
| Oct 2, 2018 at 7:43 | comment | added | Ingo Blechschmidt | Andreas Kaseorg taught me today how to remove the soundness hypothesis. Let $M$ be the machine which looks at all $T$-proofs and stops as soon as a proof of "$M$ doesn't halt" has been found. If $T$ shows that $M$ doesn't halt, then $M$ actually halts, then $T$ can prove this fact, and hence $T$ is inconsistent. Hence "$M$ doesn't halt" is a true but unprovable statement. We can further incorporate a version of Rosser's trick to show Gödel's incompletenesstheorem in full generality. (continuing) | |
| Jun 10, 2018 at 12:15 | comment | added | Ingo Blechschmidt | @Joel: Regarding your last comment, I don't see how this works. Assuming that T is complete, T shows, for any given Turing machine, that it halts or shows that it doesn't halt. How can you pass from this to a proof in T that there is a halting oracle? I'm confused because T won't prove the reflection principle for T. | |
| Jun 17, 2017 at 11:25 | comment | added | Joel David Hamkins | @gowrath Thinking about the converse is an interesting idea. I don't know any direct argument for proving that the incompleteness of PA implies the halting problem is undecidable. And given that Turing's proof of the undecidability of the halting problem is so quick, it would be hard to improve upon it. About soundness, the proof of incompletenes via the halting problem seems to use it, since one needs the veracity of the proof. But I suppose that you can eliminate this by re-proving the undecidability of the halting problem in T, thereby effectively making T sound enough for the purpose. | |
| Jun 17, 2017 at 3:54 | comment | added | gowrath | @JoelDavidHamkins Another point, you say "the same argument works for any sound computably axiomatizable theory $T$". I'm probably mistaken, but doesn't the incompleteness theorem only assume consistency (and not soundness)? If so, is it viable to prove undecidability of the halting problem implies incompleteness of T, assuming that $T$ is only consistent? I suppose the linked blog post does this when it is proving Rosser's strengthened version of the incompleteness theorem? | |
| Jun 17, 2017 at 3:40 | comment | added | gowrath | @JoelDavidHamkins Apologies for bringing up an old question, but do you have any idea where I could find a proof of the converse of this statement. You mention in the comments that there are different degrees of completions of PA, some more complicated than the halting problem, but if one were to concern themselves with completion in the sense of the incompleteness theorem, I assume the decidability of the halting problem would make PA complete? If so, could I have an idea/reference of how the proof of this might proceed? | |
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jan 6, 2016 at 7:22 | vote | accept | Symeof | ||
| Dec 30, 2015 at 21:59 | comment | added | Joel David Hamkins | @DRF Perhaps someone can suggest an exposition, but I think you can prove this without much difficulty. Start by proving that $\Sigma_n$ truth has complexity $0^{(n)}$, which is a generalization of the fact that the halting problem $0'$ is $\Sigma_1$-complete. Since the argument is uniform, it follows that full truth is $0^{(\omega)}$. | |
| Dec 30, 2015 at 21:53 | comment | added | DRF | @JoelDavidHamkins Wow really? Is there an accessible (to a set theory masters with some grounding in proof theory and computability theory but out of academia for a few years) exposition of that somewhere? | |
| Dec 30, 2015 at 20:49 | comment | added | Joel David Hamkins | For example, true arithmetic is a completion of PA with Turing complexity $0^{(\omega)}$. | |
| Dec 30, 2015 at 19:32 | comment | added | Joel David Hamkins | I agree with that statement; but perhaps it would paint a somewhat fuller picture to say that the completions of PA are branches through a certain computable tree. It follows that there are completions that are low, and these have strictly lower complexity in the Turing degrees than the halting problem. Meanwhile, other completions are far more complicated than the halting problem. | |
| Dec 30, 2015 at 19:22 | comment | added | Lucas K. | Goes also the other way. If halting problem would be decidable you could make PA complete. | |
| Dec 30, 2015 at 13:45 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |