CONCEPT
Lambda Calculus
Alonzo Church’s 1930s formal system in which everything is a function—the near-vacuum from which all of mechanical computation can be derived, and the mathematical foundation that gave the word “algorithm” its first rigorous definition.
The most radical idea in computer science is that you can build a universe out of a single verb.
Alonzo Church’s lambda calculus begins with almost nothing: a way to write a function, a way to apply it to an argument, and a rule for substituting one into the other. There are no numbers in it to start with, no logic, no data—only the operation of taking an input and producing an output, denoted with the Greek letter lambda. From this near-vacuum, Church showed that you could construct the natural numbers, arithmetic, and in principle any calculation whatsoever. The number three, for instance, is not posited but defined: it is the function that takes another function and an argument and applies that function three times. Mathematical objects we treat as primitive and concrete are, from the standpoint of computation, nothing but compressed procedures—a number is a thing you do. This insight runs underneath the whole edifice of artificial intelligence: every word,