Editing Lambda calculus (section)

{{Short description|Mathematical-logic system based on functions}}

In [[mathematical logic]], the '''lambda calculus''' (also written as '''''λ''-calculus''') is a [[formal system]] for expressing [[computability|computation]] based on function [[Abstraction (computer science)|abstraction]] and [[function application|application]] using variable [[Name binding|binding]] and [[Substitution (algebra)|substitution]]. Untyped lambda calculus, the topic of this article, is a [[universal machine]], a [[model of computation]] that can be used to simulate any [[Turing machine]] (and vice versa). It was introduced by the mathematician [[Alonzo Church]] in the 1930s as part of his research into the [[foundations of mathematics]]. In 1936, Church found a formulation which was [[#History|logically consistent]], and documented it in 1940.

Lambda calculus consists of constructing [[#Lambda terms|lambda term]]s and performing [[#Reduction|reduction]] operations on them. A term is defined as any valid lambda calculus expression. In the simplest form of lambda calculus, terms are built using only the following rules:{{efn|name=3rules|1= These rules produce expressions such as: <math>(\lambda x.\lambda y.(\lambda z.(\lambda x .z\ x)\ (\lambda y.z\ y))(x\ y))</math>. Parentheses can be dropped if the expression is unambiguous. For some applications, terms for logical and mathematical constants and operations may be included.}}

# <math display="inline">x</math>: A [[#validLambdaVar|variable]] is a character or string representing a parameter.
# <math display="inline">(\lambda x.M)</math>: A [[#lambdaAbstr|lambda abstraction]] is a function definition, taking as input the bound variable <math>x</math> (between the λ and the punctum/dot '''.''') and returning the body <math display="inline">M</math>.
# <math display="inline">(M\ N)</math>: An [[#anApplic|application]], applying a function <math display="inline">M</math> to an argument <math display="inline">N</math>. Both <math display="inline">M</math> and <math display="inline">N</math> are lambda terms.

The reduction operations include:

* <math display="inline">(\lambda x.M[x])\rightarrow(\lambda y.M[y])</math> : [[#α-conversion|α-conversion]], renaming the bound variables in the expression. Used to avoid [[name collision]]s.
* <math display="inline">((\lambda x.M)\ N)\rightarrow (M[x:=N])</math> : [[#β-reduction|β-reduction]],{{efn|name=beta|1= Barendregt, Barendsen (2000) call this form 
*''axiom β'': (λx.M[x]) N = M[N] , rewritten as (λx.M) N = M[x := N], "where M[x := N] denotes the substitution of N for every occurrence of x in M".<ref name="BarendregtBarendsen"/>{{rp|7}} Also denoted M[N/x], "the substitution of N for x in M".<ref>{{nlab|id=explicit+substitution|title=explicit substitution}}</ref>}} replacing the bound variables with the argument expression in the body of the abstraction.

If [[De Bruijn index]]ing is used, then α-conversion is no longer required as there will be no name collisions. If [[Reduction strategy (lambda calculus)|repeated application]] of the reduction steps eventually terminates, then by the [[Church–Rosser theorem]] it will produce a [[Beta normal form|β-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.