How can a whole language be built from functions alone?
With only variables, functions and function calls, you can build numbers, loops and any computation a computer can do.
▶ Start the storyIt can be done because functions alone can stand in for numbers, arithmetic and repetition, as an idea from the 1930s showed. The lambda calculus, introduced by the mathematician Alonzo Church while researching the foundations of mathematics, is a for expressing computation based on function abstraction and application. A term in it is built by repeating three rules, which cover variables, (functions) and applications (calling a function on something). That is the whole language, and yet untyped lambda calculus is a universal model of computation: it can simulate any , and a Turing machine can simulate it.
How do you get numbers out of nothing but functions? Church's trick was to define the number n as a function that takes another function f and returns f composed with itself n times. A good way to think of it is the instruction "repeat n times". Because numbers are functions, arithmetic becomes function building: multiplying Church numerals is simply composing them as functions.
Step 1: Start with a function f
Any single-step action
Step 2: n
Takes f and returns f composed with itself n times
Step 3: Three means do it three times
The number is the 'repeat n times' instruction
Step 4: Multiplication
Simply composing the numerals as functions
Even loops come out of it. Lambda calculus has no names for terms, only parameter names, but a lambda expression can receive itself as its own argument and refer to a copy of itself through that parameter's name. That is , with no naming needed.
Church's first version of the system was shown to be logically inconsistent in 1935. In 1936 he isolated and published just the portion relevant to computation, the untyped lambda calculus. Alan Turing enrolled at Princeton under Church, and together they showed that the lambda calculus and the were equivalent in capabilities. For decades it was only a formalism. When its relation to programming languages was clarified in the 1960s, it became a foundation: implement it, and Lisp was influenced by Church's notation.
Quiz me
0/3
Recap
A language built from only functions can still compute anything, because numbers, loops and recursion can all be made out of functions.
💡 A trick to remember it · Three is just 'do it three times', so numbers are functions wearing a number's hat.
Surprising fact · Church's first version was shown to be inconsistent in 1935, and the part about computation survived.
Connects to
Sources (3)
No source, no claim. Every fact in this lesson (15 claims) cites at least one of these.