Lambda calculus information

Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics.

Lambda calculus consists of constructing lambda terms and performing reduction operations on them. In the simplest form of lambda calculus, terms are built using only the following rules:^[a]

${\textstyle x}$ : A variable is a character or string representing a parameter.
${\textstyle (\lambda x.M)}$ : A lambda abstraction is a function definition, taking as input the bound variable $x$ (between the λ and the punctum/dot .) and returning the body ${\textstyle M}$ .
${\textstyle (M\ N)}$ : An application, applying a function ${\textstyle M}$ to an argument ${\textstyle N}$ . Both ${\textstyle M}$ and ${\textstyle N}$ are lambda terms.

The reduction operations include:

${\textstyle (\lambda x.M[x])\rightarrow (\lambda y.M[y])}$ : α-conversion, renaming the bound variables in the expression. Used to avoid name collisions.
${\textstyle ((\lambda x.M)\ N)\rightarrow (M[x:=N])}$ : β-reduction,^[b] replacing the bound variables with the argument expression in the body of the abstraction.

If De Bruijn indexing is used, then α-conversion is no longer required as there will be no name collisions. If repeated application of the reduction steps eventually terminates, then by the Church–Rosser theorem it will produce a β-normal form.

Variable names are not needed if using a universal lambda function, such as Iota and Jot, which can create any function behavior by calling it on itself in various combinations.

Cite error: There are <ref group=lower-alpha> tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).

^ Cite error: The named reference BarendregtBarendsen was invoked but never defined (see the help page).
^ explicit substitution at the nLab

[BarendregtBarendsen-2] Cite error: The named reference BarendregtBarendsen was invoked but never defined (see the help page).

[3] xplicit substitution at the nLab

Lambda calculus information

and 19 Related for: Lambda calculus information

Lambda calculus

Typed lambda calculus

Simply typed lambda calculus

Knights of the Lambda Calculus

Combinatory logic

System F

Church encoding

Dependent type

Calculus of constructions

Lambda calculus definition

SKI combinator calculus

Lambda

Programming language theory

Lambda cube

Anonymous function

List of functional programming topics

Intuitionistic logic

Canonical form

Alonzo Church