the lambda calculus

Forget tapes, states, and machines for a moment. Imagine computation built entirely out of functions, things that take an input and give back a result, and nothing else: no numbers, no memory cells, just functions taking functions and returning functions. It sounds impossibly austere, yet it is enough to express any computation at all. The lambda calculus, invented by Alonzo Church in the 1930s, is exactly this: a tiny language whose only ingredients are variables, a way to make a function, and a way to apply one function to another.

There are just three forms of expression. A variable like x. An abstraction (lambda x. M), read 'the function that takes x and returns M', which is how you build a function. And an application (M N), read 'apply function M to argument N'. Computation is a single rewriting rule called beta reduction: to evaluate ((lambda x. M) N), substitute N for every x in M. For instance (lambda x. x) applied to y reduces to y, so (lambda x. x) is the identity function. Astonishingly, you can encode numbers as functions (the Church numerals: 0 is lambda f. lambda x. x, 1 is lambda f. lambda x. f x, n applies f n times), and from there encode addition, multiplication, booleans, pairs, and recursion, all as pure functions.

The lambda calculus matters for two reasons. First, it computes exactly the Turing-computable functions, no more and no less, even though it has no notion of a tape, a step counter, or a current state. This independent convergence with Turing's model is a cornerstone of the evidence for the Church-Turing thesis. Second, it is the theoretical seed of functional programming: languages like Lisp, Haskell, and the lambdas now found in nearly every modern language descend directly from it. The honest caveat is that 'equivalent in power' does not mean 'convenient', raw lambda calculus is painfully low-level to program in, just as a bare Turing machine is.