# Alonso Churh's proof that first order logic is undecidable.

**URL:** <https://boards.straightdope.com/t/alonso-churhs-proof-that-first-order-logic-is-undecidable/344939>\
**Category:** Factual Questions\
**Created:** [February 17, 2006, 1:27pm UTC](https://boards.straightdope.com/t/alonso-churhs-proof-that-first-order-logic-is-undecidable/344939 "2006-02-17T13:27:00Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\
**Post date:** [February 17, 2006, 1:27pm UTC](https://boards.straightdope.com/t/alonso-churhs-proof-that-first-order-logic-is-undecidable/344939/1 "2006-02-17T13:27:00Z")

</div>

I took a course in computability and intractability this semester. The course centres around Turing’s work, only mentioning Church in the context of the Church-Turing thesis. My understanding is that Church actually showed that not all problems were decidable before Turing was able to. It’s also my understanding that Church showed this in a radically different way to Turing, using his lambda calculus.

Is there a decent overview of Church’s argument anywhere? How complicated was Church’s argument? Why did it never catch on in the way that Turing’s argument did (maybe it did, but from my perspective, it seems that Turing’s machines are much more pervasive in the teaching of computability theory than lambda calculus).

---

<div class="post-metadata">

**Author:** ![Exapno\_Mapcase](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/exapno_mapcase/32/1051_2.png) [@Exapno\_Mapcase](https://boards.straightdope.com/u/Exapno_Mapcase)\
**Post date:** [February 17, 2006, 2:17pm UTC](https://boards.straightdope.com/t/alonso-churhs-proof-that-first-order-logic-is-undecidable/344939/2 "2006-02-17T14:17:18Z")

</div>

I’m a bit confused. Wasn’t the incompleteness theorem a work of Gödel , rather than Turing?

[http://www-history.mcs.st-and.ac.uk/Mathematicians/Church.html](http://www-history.mcs.st-and.ac.uk/Mathematicians/Church.html)

> [@](#):
>
> Church is probably best remembered for ‘Church’s Theorem’ and ‘Church’s Thesis’ both of which first appeared in print in 1936. Church’s Theorem, showing the undecidability of first order logic, appeared in A note on the Entscheidungsproblem published in the first issue of the Journal of Symbolic Logic. This, of course, is in contrast with the propositional calculus which has a decision procedure based on truth tables. Church’s Theorem extends the incompleteness proof given of Gödel in 1931.

---

<div class="post-metadata">

**Author:** ![CookingWithGas](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/cookingwithgas/32/485_2.png) [@CookingWithGas](https://boards.straightdope.com/u/CookingWithGas)\
**Post date:** [February 17, 2006, 2:36pm UTC](https://boards.straightdope.com/t/alonso-churhs-proof-that-first-order-logic-is-undecidable/344939/3 "2006-02-17T14:36:51Z")

</div>

[QUOTE=Exapno Mapcase]  
Wasn’t the incompleteness theorem a work of Gödel , rather than Turing?  
[/QUOTE]  
Gödel wrote the incompleteness theorem, but I think Turing said that given a problem fed to a Turing Machine, it was not possible to determine _a priori_ whether a Turing Machine would terminate or run forever. I am not at all familiar with Church.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [February 17, 2006, 2:47pm UTC](https://boards.straightdope.com/t/alonso-churhs-proof-that-first-order-logic-is-undecidable/344939/4 "2006-02-17T14:47:03Z")

</div>

Turing and Church both published in 1936. Since Turing was one of Church’s graduate students, it’s likely that they had some influence over each other.

---

<div class="post-metadata">

**Author:** ![bonzer](https://avatars.discourse-cdn.com/v4/letter/b/45deac/32.png) [@bonzer](https://boards.straightdope.com/u/bonzer)\
**Post date:** [February 17, 2006, 7:22pm UTC](https://boards.straightdope.com/t/alonso-churhs-proof-that-first-order-logic-is-undecidable/344939/5 "2006-02-17T19:22:42Z")

</div>

[QUOTE=ultrafilter]  
Turing and Church both published in 1936. Since Turing was one of Church’s graduate students, it’s likely that they had some influence over each other.  
[/QUOTE]

Both probably reached their main results completely independently, but Turing wrote his big paper on the subject knowing what Church had already done.  
Church had published a closely related paper a year earlier, but there’s no evidence that Turing had seen it. Turing had already started explaining his results to others in Cambridge and submitted an abstract (to _Comptes Rendus_) when Church’s key paper arrived, surprising everybody. Max Newman then promptly wrote to Church in Princeton to tell him that Turing had reached the same conclusion via a different route.  
With everybody involved now knowing what the two had done, it was only then that Turing went to Princeton as a grad student and it was there he wrote up his proof. Obviously there was then regular interaction between the two and that no doubt had some influence on how Turing polished it up, but the whole point by then was how radically different his approach was compared to Church’s.  
I get the impression that the two weren’t particularly close at Princeton: Church suggested his thesis topic, but Turing was both a bit of a loner and not really in need of advice.

More broadly, them both coming up with different proofs independently isn’t that surprising, since it was - thanks to Hilbert - a hot problem that quite a few people were working on at the time.
