Lambda calculus

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.

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  could take the place of every spot in a function where the variable  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.

## Syntax

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

- Any symbol or word (, , , or anything else) is called a _variable_.
- _Abstractions_ are always in the form of  with  indicating the start of an abstraction,  being any variable, and  being the function definition (like  would take in  and return .)
- An _application_ is actually setting  (the variable) to equal something, in the form  ( is input). an example would be  , with  being the function,  being the input and   being the abstraction.
For the application and abstraction examples,  and  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.

## Reduction and Conversion

There are three types of reduction: _α-conversion_, _β-reduction_, and _η-conversion_.

- α-conversion states that  is exactly the same as , as long as they are separate. Variable names are only to distinguish between functions and/or inputs.
- β-reduction states that   ( as the function,  as the input) and  are the same. You destroy the , (leaving only ) and replace all instances of  with . this results in , which simplifies to . This is the most important one, and is the basis of lambda calculus.
- η-conversion states that  is not needed, and that it converts to . However, , cannot be η-converted. This is because  outputs , and this means that the  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).

### Common mistakes

this is incorrect because  is using the variable .  If it was , conversion could be done.

it should equal  .

you cannot get rid of the . This is because

## Encoding and Datatypes

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.

### Church numerals

**church numerals** use the following encoding standards (rules):

_Note: Church numerals are made for whole numbers. There are other standards for encoding for all rational numbers._

Because of the syntax of lambda calculus, numbers are also functions, and can take in inputs; all functions can output another function as a result. Numeral _n_ applies _x_ to _f_, _n-_times. This is very useful as a repeat _n_ times function.

### Booleans and Logic Gates

Booleans can be thought of as a lightbulb: they can be on or off (`true` or `false`). Typically, you use **church booleans** for representing these.

- (a function that takes in two values and returns the first one) for `true`.
- (a function that takes in two values and returns the second one) for `false`.

From these, you can make logic gates and conditionals.

The and logic gate takes in two inputs and returns `true` if both of them are `true`. It is defined as

The other gates — or, xor, and not — are below.

Nand, nor, xnor can be made by combining these gates.