Church's lambda calculus and the Entscheidungsproblem
- logic
- american
Alonzo Church’s 1930s work used the lambda calculus to formalize effective calculation through abstraction, application and substitution. In 1936 he established a negative solution to the decision problem for first-order logic. The result helped show that some requests for a universal mechanical decision procedure are mathematically impossible. It belongs to the same foundational transformation as Turing’s independent machine-based analysis, although the models look very different. Lambda calculus also became influential in programming-language theory, a later application distinct from its original role in logic and foundations. **Timeline anchor:** 1 January 1936 CE. **References:** [Source 1](https://en.wikipedia.org/wiki/Lambda_calculus), [Source 2](https://en.wikipedia.org/wiki/Entscheidungsproblem).
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 undecidability on The history of computer science by @athan
- Hilbert's Entscheidungsproblem on The history of computer science by @athan
- Church and Turing: computability on Type theory and functional programming: a history by @athan
- Church introduces the lambda calculus on Type theory and functional programming: a history by @athan
Open Church's lambda calculus and the Entscheidungsproblem in the timeline