Church and Turing: computability
- lambda calculus
- logic
Alonzo Church used the lambda calculus and related formal work in the 1930s to investigate effective calculability. His 1936 undecidability result showed that there is no general mechanical procedure for solving the decision problem for first-order logic. Lambda calculus represents computation through abstraction and application, making substitution central to evaluation. Church’s result helped establish that limits on algorithms can be proved mathematically, rather than attributed only to inadequate hardware. Alan Turing reached a corresponding negative result through a different model. Their convergence supports the conceptual framework connecting formally defined computation with the intuitive idea of an effective procedure. **Timeline anchor:** 1 January 1936 CE. Year of publication. **References:** [Source 1](https://en.wikipedia.org/wiki/Church–Turing_thesis), [Source 2](https://en.wikipedia.org/wiki/Entscheidungsproblem).
Sources
Related
On other timelines
- Hilbert's Entscheidungsproblem on The history of computer science by @athan
- Church's lambda calculus and the Entscheidungsproblem on The history of mathematics by @athan