In mathematical logic and computer science, lambda calculus, also λ-calculus, is a formal system (a system that can be used to figure out different logical theories and ideas). It was made to explore different ways of creating and using mathematical functions, and it lays out rules for doing this. It is also a tool for exploring recursion, and it has been used to explain what a computable function is. It was made by Alonzo Church and Stephen Cole Kleene in the 1930s. In 1936, Church used lambda calculus to show that there is no solution to the Entscheidungsproblem.^[1][2]

Lambda calculus can be called the smallest universal programming language. At its core, lambda calculus is made up of just one transformation rule (something called variable substitution) and just one way to define a function. Each function definition has a list of the function's parameters, which are all of the variables that can be used in that function. Variable substitution is where specific variables in a function are replaced by other values (for example, the value 👁 {\displaystyle 2}
could take the place of every spot in a function where the variable 👁 {\displaystyle x}
appears). This is called a transformation rule because it can be used to transform lambda expressions by changing around their values.

Lambda calculus is considered "universal" because it can be used to both create and find the answer to any computable function. This is exactly what a Turing machine can do, so lambda calculus and Turing machines are said to be equivalent. However, lambda calculus focuses more on the use of transformation rules. It does not care about the actual machine that puts those rules into place. It is an approach more related to software than to hardware.

There is no way to answer the question of whether two lambda calculus expressions are the same as each other (in more specific words, there is no general algorithm that can show that two lambda expressions are equivalent). This was the first problem where the idea of undecidability could be proven. Later, undecidability was also proven for the halting problem, where it was shown that there is no general way to show whether or not a program will keep running forever. Lambda calculus has had large effects on lots of functional programming languages, such as LISP, ML, and Haskell.

Lambda calculus has simple syntax (rules). Every program is made of lambda terms which are as follows:

• Any symbol or word (👁 {\displaystyle x}
  , 👁 {\displaystyle y}
  , 👁 {\displaystyle foo}
  , or anything else) is called a variable.
• Abstractions are always in the form of 👁 {\displaystyle \lambda x.M}
  with 👁 {\displaystyle \lambda }
  indicating the start of an abstraction, 👁 {\displaystyle x}
  being any variable, and 👁 {\displaystyle M}
  being the function definition (like 👁 {\displaystyle \lambda x.x+2}
  would take in 👁 {\displaystyle x}
  and return 👁 {\displaystyle x+2}
  .)
• An application is actually setting 👁 {\displaystyle x}
  (the variable) to equal something, in the form 👁 {\displaystyle \lambda x.MN}
  (👁 {\displaystyle N}
  is input). an example would be 👁 {\displaystyle \lambda x.x+2}
  👁 {\displaystyle 5}
  , with 👁 {\displaystyle \lambda x.x+2}
  being the function, 👁 {\displaystyle 5}
  being the input and 👁 {\displaystyle \lambda x.x+2}
  👁 {\displaystyle 5}
  being the abstraction.

For the application and abstraction examples, 👁 {\displaystyle x+2}
and 👁 {\displaystyle 5}
were used. This is not valid lambda calculus, as the only valid syntax are the lambda terms shown above. There are ways to emulate addition, numerals, strings (words), and any other mathematical concept in lambda calculus.^[3]

There are three types of reduction: α-conversion, β-reduction, and η-conversion.

• α-conversion states that 👁 {\displaystyle \lambda x.x}
  is exactly the same as 👁 {\displaystyle \lambda y.y}
  , as long as they are separate. Variable names are only to distinguish between functions and/or inputs.
• β-reduction states that 👁 {\displaystyle \lambda x.x+2}
  👁 {\displaystyle 5}
  (👁 {\displaystyle \lambda x.x+2}
  as the function, 👁 {\displaystyle 5}
  as the input) and 👁 {\displaystyle 5+2}
  are the same. You destroy the 👁 {\displaystyle \lambda x}
  , (leaving only 👁 {\displaystyle x+2}
  ) and replace all instances of 👁 {\displaystyle x}
  with 👁 {\displaystyle 5}
  . this results in 👁 {\displaystyle 5+2}
  , which simplifies to 👁 {\displaystyle 7}
  . This is the most important one, and is the basis of lambda calculus.
• η-conversion states that 👁 {\displaystyle \lambda x.\lambda y.y}
  is not needed, and that it converts to 👁 {\displaystyle \lambda y.y}
  . However, 👁 {\displaystyle \lambda x.\lambda y.x}
  , cannot be η-converted. This is because 👁 {\displaystyle \lambda y.x}
  outputs 👁 {\displaystyle x}
  , and this means that the 👁 {\displaystyle \lambda x}
  at the beginning is necessary; β-reduction should be used if you can use it. This is the least common type and can be ignored most of the time.

You perform each type or reduction if you can. Once it can no longer be simplified, the program has halted (stopped).

Because of the limited syntax, it may seem impossible to make numbers or strings or anything else that many programming languages have, but it's a matter of encoding. Lambda calculus compensates for this by using the methods demonstrated in the sections below.