This post is my note for What is seminar on Lambda Calculus.
Lambda calculus was created by Alonzo Church in the 1930s, and was used by him to solve Entscheidungsproblem in 1936, which is related to Hilbert's tenth problem. In the same year, Alan Turing independently solved Entscheidungsproblem using his invention Turing machine. Shortly after, Turing realized that these two models are actually equivalent as models of computation.
In this note, I will first give the formal definition of lambda expressions. Then with the help of Python, I am going to show how to do Boolean algebra and basic arithmetic using lambda calculus, which to some extend gives an illustration that Turing machine and lambda calculus are equivalent.
Lambda calculus consists of lambda expressions and operations on them. There are three basic elements in Lambda expression:
- variables: x, y, z, ...
- symbols in abstraction: λ and .
- parentheses for association: ()