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).
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.
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.
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.