Church's lambda calculus and undecidability
- theory
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 April 1936 CE. Approximate day. **References:** [Source 1](https://en.wikipedia.org/wiki/Lambda_calculus), [Source 2](https://en.wikipedia.org/wiki/Alonzo_Church).
Sources
Related
On other timelines
- Lambda calculus supplies an untyped functional foundation on Dynamically typed functional programming · Lisp, Scheme, Clojure and teaching traditions by @athan
- Church's lambda calculus and the Entscheidungsproblem on The history of mathematics by @athan
- Church introduces the lambda calculus on Type theory and functional programming: a history by @athan
Open Church's lambda calculus and undecidability in the timeline