On this page
What was the decision problem that puzzled mathematicians?
In 1928, German mathematician David Hilbert posed the *Entscheidungsproblem*, or decision problem: could a single, mechanical procedure decide whether any given statement in first-order logic was valid? Mathematics lacked a precise definition of an "effective calculation" or algorithm. Without one, no one could prove whether such a universal problem solver was possible.
At Princeton University, American logician Alonzo Church tackled this question. Working alongside doctoral students Stephen Kleene and J. Barkley Rosser in the early 1930s, Church sought a formal system built purely on functions to capture the essence of mechanical calculation.
When learners first encounter abstract logic and foundational theories, connecting disparate definitions can feel overwhelming. The Fermi Concept Library maps every concept in physics, chemistry, biology, mathematics and computing, each with its own lesson and its place in the map.
How does Alonzo Church's lambda calculus actually work?
Church's framework, the lambda calculus, stripped computation down to three rules: variables, function abstraction, and function application. As the Stanford Encyclopedia of Philosophy entry on the lambda calculus notes, any valid expression relies entirely on:
Variables: letters such as x, y, or z standing for values or functions.
Abstraction: defining an anonymous function by binding a parameter, written λx. M.
Application: applying a function M to an argument N, written side by side as M N.
Instead of memory registers or mutable loops, computation proceeds by rewriting terms. The core engine is beta-reduction: in an application (λx. M) N, you substitute argument N for every free occurrence of x in M.
In a 1936 paper in the Transactions of the American Mathematical Society, Church and Rosser proved the Church-Rosser theorem. If an expression can be simplified to an irreducible normal form, that final result is unique regardless of reduction order.
How do Church numerals represent numbers through functions?
Because the calculus contains only functions, Church encoded natural numbers as higher-order functions. In his 1936 paper in the American Journal of Mathematics, each integer n is defined by applying a function f to an argument x exactly n times:
Zero: λf. λx. x
One: λf. λx. f x
Two: λf. λx. f (f x)
Any integer n: λf. λx. fⁿ x
To calculate, Church defined a successor function, SUCC = λn. λf. λx. f (n f x). Evaluating SUCC applied to one illustrates beta-reduction in four steps:
Application: (λn. λf. λx. f (n f x)) (λf. λx. f x)
Substitute one for n: λf. λx. f ((λf. λx. f x) f x)
Apply to argument f: λf. λx. f ((λx. f x) x)
Apply to argument x: λf. λx. f (f x)
The result applies f twice to x, matching Church's definition of two.
Following multi-step algebraic substitutions by hand often invites minor errors. The Fermi Problem Library provides worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
Why did Church's discovery prove that some problems are unsolvable?
With computation formally defined, Church tested its limits. In the American Journal of Mathematics, he proved that no lambda-definable function can decide whether an arbitrary lambda expression will ever terminate into a normal form. Expressions such as (λx. x x) (λx. x x) loop infinitely without terminating, and no algorithm can systematically identify in advance whether an arbitrary term has a normal form.
Church then extended this finding to formal logic in the Journal of Symbolic Logic. He demonstrated that solving Hilbert's *Entscheidungsproblem* would require deciding whether arbitrary lambda terms have normal forms. Because that decision is provably impossible, first-order logic is undecidable: no universal algorithm can verify every mathematical truth.
This milestone showed that mathematics has inherent computational boundaries, later inspiring Julia Robinson's work on undecidability and Hilbert's tenth problem.
How did Church and Alan Turing unite the theory of computation?
Months later, Alan Turing reached the same conclusion using an idealized machine with a tape and scanner. In Alan Turing's 1936 paper on computable numbers, published in the Proceedings of the London Mathematical Society, Turing introduced what we now call Turing machines.
Turing arrived at Princeton in late 1936 to work with Church as a doctoral student, having demonstrated in an appendix to his paper that Turing computability and lambda-definability are mathematically equivalent. As detailed in the Stanford Encyclopedia of Philosophy entry on the Church-Turing thesis, this equivalence consolidated the Church-Turing thesis: every algorithmically computable process can be represented by these systems.
While Turing machines shaped computer hardware, lambda calculus became the foundation of functional programming. Decades later, John McCarthy's work creating LISP borrowed Church's lambda notation to treat functions as first-class values.
For students exploring abstract logic and proofs, Fermi's AI tutor works out what you already know, builds a plan for the session, and teaches through it.
