<p>I believe that some version of this connection can be tied back to <a href="https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf" rel="noreferrer">Turing's seminal paper on computability</a>.</p>

<p>Namely, Turing makes the following two claims:</p>

<ol>
<li>"The results of Section 8 have some important applications. In particular, they can  be used  to  show that  the  Hilbert Entscheidungsproblem can  have no solution."</li>
<li>"If the negation of what Godel has shown had been proved, i.e. if, for each <span class="math-container">$U$</span> either <span class="math-container">$U$</span> or <span class="math-container">$\neg U$</span> is provable, then  we should have an immediate solution of the Entscheidungsproblem."</li>
</ol>

<p>The conclusion, I believe, follows from Modus Tollens.</p>

CC BY-SA 4.0
2019-02-15T03:13:05.210Z
2019-02-15T03:13:05.210Z
Yonatan N
<p>A weaker form of Gödel's First Incompleteness Theorem, direct proofs of which in Gödel's manner are lengthy, involved and at some place rather counter-intuitive, has a simple and intuitive proof based on the undecidability of the halting problem - see for example <a href="https://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof" rel="noreferrer">https://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof</a></p>

<p>Who first proposed this proof and in what article or book has it been first published?</p>

<cc.complexity-theory><lo.logic><halting-problem>
What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?
François Bry
# What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?

(Asked by: username_0 on 2019-02-14)

A weaker form of Gödel's First Incompleteness Theorem, direct proofs of which in Gödel's manner are lengthy, involved and at some place rather counter-intuitive, has a simple and intuitive proof based on the undecidability of the halting problem - see for example <https://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof>

Who first proposed this proof and in what article or book has it been first published?

**Tags:** cc.complexity-theory, lo.logic, halting-problem


---

## 1 answers

### Answer by username_1 on 2019-02-15. Score: 9 | Accepted answer

I believe that some version of this connection can be tied back to [Turing's seminal paper on computability](https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf).

Namely, Turing makes the following two claims:

1. "The results of Section 8 have some important applications. In particular, they can be used to show that the Hilbert Entscheidungsproblem can have no solution."
2. "If the negation of what Godel has shown had been proved, i.e. if, for each $U$ either $U$ or $\neg U$ is provable, then we should have an immediate solution of the Entscheidungsproblem."

The conclusion, I believe, follows from Modus Tollens.


---

