For questions on the formal system in mathematical logic for expressing computation using abstract notions of functions and combining them through binding and substitution.
Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic and theoretical computer-science for expressing computation based on function abstraction and application using variable binding and substitution. Its namesake, the Greek letter lambda (λ), is used in lambda expressions and lambda terms to denote binding a variable in a function.
It was first introduced by mathematician Alonzo Church in the 1930s as part of his research of the foundations of mathematics. The original system was shown to be logically inconsistent because of the Kleene–Rosser paradox. Subsequently, in 1936 Church isolated and published just the portion relevant to computation, what is now called the untyped lambda calculus.
Untyped lambda calculus is Turing complete, that is, it is a universal model of computation that can be used to simulate any turing-machine (see computability). It may be used to model booleans, arithmetic, data structures and recursion.
Lambda calculus may be untyped or typed. In typed lambda calculus (see type-theory), functions can be applied only if they are capable of accepting the given input's "type" of data. Typed lambda calculi are weaker than the untyped lambda calculus, in the sense that typed lambda calculi can express less than the untyped calculus can, but on the other hand typed lambda calculi allow more things to be proved; in the simply typed lambda calculus it is for example a theorem that every evaluation strategy terminates for every simply typed lambda-term, whereas evaluation of untyped lambda-terms need not terminate. One reason there are many different typed lambda calculi has been the desire to do more (of what the untyped calculus can do) without giving up on being able to prove strong theorems about the calculus.
Typed lambda calculi are closely related to mathematical logic and proof-theory via the Curry–Howard isomorphism: types correspond to logic formulas, lambda-terms correspond to derivations in a logic system (depending on the kind of typed lambda calculus) and computation steps in the lambda calculus correspond to normalization (i.e. cut-elimination) steps for derivations.
Lambda calculus has applications in many different areas in mathematics, philosophy, linguistics, and computer science. Lambda calculus has played an important role in the development of the theory of programming languages, since functional programming languages implement the lambda calculus. Lambda calculus also is a current research topic in category-theory.
