The lambda calculus and an unsolvable problem
Era 1 · The foundations (1763–1942) › Computability
- Lineage
- Symbols and logic
- Kind
- Publication
Who
Princeton University
What happened
In April 1936, in the American Journal of Mathematics, Alonzo Church publishes "An Unsolvable Problem of Elementary Number Theory," presented to the American Mathematical Society a year earlier.
Why it mattered
It proposes that what is effectively calculable is what can be expressed in the lambda calculus, and with that definition it proves that some problems have no mechanical solution. Shortly afterward Church applies this to the Entscheidungsproblem, with a negative answer.
The full story
Alonzo Church, a professor at Princeton, had been developing a formal system called the lambda calculus since the early 1930s with two students, Stephen Kleene and J. Barkley Rosser. In it, everything is built from functions: defining them and applying them to arguments. Even numbers are functions: 2 is the function that applies another function twice. Kleene showed that this spare system could express the usual arithmetic functions, and Church and Kleene proved that the functions definable in it are the same as the recursive functions Gödel had studied.
That led Church to a bold proposal: a function on numbers is effectively calculable, that is, computable by a mechanical procedure, only if it can be defined in the lambda calculus. This is what is now called Church's thesis. It cannot be proved, because it equates an intuitive idea with a mathematical definition, but it finally gives something precise to work with.
With that definition, the paper published in April 1936 constructs a problem in number theory that no mechanical procedure can solve. Shortly afterward, in a brief note in the first volume of the Journal of Symbolic Logic, Church applied the result to Hilbert and Ackermann's decision problem: there is no general method for deciding whether a formula of first-order logic is valid.
Gödel was not persuaded by Church's proposal. What persuaded Gödel was Turing's, published a few months later, which reached the same boundary from a different direction.
Under the hood
The lambda calculus has only three things: variables, function definition (λx.M, "the function that maps x to M"), and the application of a function to an argument (M N). Computing means substituting: (λx.M) N reduces to M with N in place of x.
Numbers are represented as functions. The number 2 is λf.λx.f(f x): it takes a function and applies it twice. With these definitions Church and Kleene expressed addition, multiplication, and every recursive function. The lambda calculus is the direct ancestor of functional programming languages, starting with Lisp.
Builds on
The Entscheidungsproblem (1928)
Documented direct influence
Both papers answer the Entscheidungsproblem; Turing's names it in its title
Leads to
On Computable Numbers (November 30, 1936)
Independent convergence
The same result, reached independently
Finite Combinatory Processes (September 1936)
Documented direct influence
From its first sentence the paper presents itself as a development in the line of Gödel's incompleteness theorem and Church's unsolvable problems
Threads that pass through here
- From Hilbert's question to the universal machine (step 5 of 7)
Sources
Original source
Scholarship and context
How to cite
“The lambda calculus and an unsolvable problem.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/church-lambda-calculus
This entry was last reviewed on November 13, 2026.