Computation from almost nothing
Alonzo Church’s claim in the 1930s was that computation itself, the idea of a function being calculable by some definite step-by-step procedure, could be captured entirely by a formal system built from almost nothing: variables, a rule for building an unnamed function out of an expression, and a rule for applying that function to an argument. A single further rule, substitution, carries out the actual work of computing by replacing a function’s parameter with whatever it is being applied to and simplifying the result. Church proposed that this minimal apparatus, later called lambda calculus, was not merely one useful notation among several but a complete account of what it means for something to be computable at all, a claim about the foundations of mathematics and logic rather than a piece of engineering.
An inconsistency, then a fix
The route to that claim was not smooth. Church’s original system, aimed at the foundations of logic more broadly, turned out to be inconsistent, a flaw Stephen Kleene and Barkley Rosser demonstrated in 1935. Church responded in 1936 by isolating just the fragment concerned with computation, publishing a paper that both introduced what is now called untyped lambda calculus and used it to show that a central decision problem in logic, the question of whether a general procedure could determine the truth of any mathematical statement, has no such procedure at all. Alan Turing arrived at Princeton as Church’s student that same year, having independently proposed his own machine-based account of computation, and the two men established that lambda calculus and Turing machines compute exactly the same class of functions, a result now known as the Church-Turing thesis. In 1940 Church introduced a typed version of the system, weaker but free of the earlier inconsistency.
What the theorems deliver
Several of the central results have proved completely durable. The Church-Rosser theorem, showing that different orders of carrying out a computation in the calculus reach the same final answer whenever any order reaches one at all, has stood as rigorous mathematics since it was proved. The equivalence with Turing machines has likewise held without qualification, and it remains the standard justification for treating the two frameworks as interchangeable descriptions of computability. The practical encodings built on top of the calculus work exactly as designed too: numbers, true and false, and recursive functions built through a fixed-point construction can all be represented purely as functions acting on functions, with no other machinery required, and these encodings became the direct template for how functional programming languages are built.
Where it doesn’t resolve
The calculus is not always well-behaved, and that turns out to be as important as what it can do. Some expressions in the untyped system never reach a final, simplified form under any order of computation at all, so the system as a whole is not guaranteed to terminate. There is also no general procedure that can decide, given two arbitrary expressions in the calculus, whether they are equivalent to each other, a result that stands as the first problem ever formally proved undecidable. Even a smaller historical detail resists tidy resolution: Church once explained where the Greek letter used for function abstraction in his notation came from, tracing it to an earlier logical notation, then later suggested the choice had been closer to accidental, a loose thread in an otherwise carefully documented history.
From logic to programming languages
The influence of this formal system reaches well past logic. Functional programming languages implement its core operations, abstraction and substitution, in largely unchanged form, and the anonymous “lambda” functions now built into many mainstream languages that were never designed around this paradigm are a direct, named borrowing from Church’s notation. A typed version of the calculus also turned out to correspond precisely, construction for construction, to systems of formal logical proof, a correspondence that links a tool built to describe computation with a tool built to describe mathematical reasoning, and that now underlies how some software used to verify mathematical proofs is constructed. A formalism proposed to settle a question in the foundations of logic ended up supplying the working vocabulary of an entire style of programming decades later.
Is it worth your time
This is worth understanding because so little of it is arbitrary: three basic constructs and one reduction rule turn out to be enough to build arithmetic, logic and recursion from scratch, and every later development, typed variants, the connection to formal proof, functional programming itself, follows fairly directly from that minimal starting point. Readers who want to see how a foundational question in 1930s logic quietly became the basis of a programming style used today will find the whole chain laid out clearly. It rewards less anyone hoping for a system with no rough edges: some expressions simply never resolve, equivalence between two expressions cannot always be decided by any algorithm, and even the origin of its central symbol is something its inventor described two different ways.