9
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

I believe that some version of this connection can be tied back to Turing's seminal paper on computability.

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.

$\endgroup$

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.