Tutorial Introduction to Lambda Calculus

The λ calculus can be called the smallest universal programming language of the world. The λ calculus consists of a single transformation rule (variable substitution) and a single function definition scheme. It ws introduced in the 1930s by Alonzo Church as a way of formalizing the concept of effective computability. The λ calculus is universal in the sense that any computable function can be expressed and evaluated using this formalism. It is thus equivalent to Turing machines.