202303150203
Type :Note Tags : Lambda Calculus
Lambda Calculus
Lambda Calculus also knows as -Calculus is a model of computation developed by Alonzo Church in the 1930s.
One of the important things it deals with is :- The way we usually define functions is Extrinsional, as in, a function is uniquely defined by the relation it crates between its inputs and outputs, while this way to identify a function is good for most of mathematics, it is important to define the exact way in which a function computes. This problem is solved by lambda calculus making it an Intrinsional Syntax for function defintion. It captures an intrinsional definition of a function in its very minimal syntax and simple evaluation rules.
The interesting thing about lambda calculus is that, in the world of lambda calculus, there are ONLY functions, no values, no constants… Then what do functions act on? Other functions!!!
But even with this restrictions, this model of computation is Turing Complete, as in its a Universal Computation Model This was done by finding a set of computable functions by calculus which was later found to be the same as the set of functions computable by Turing Machines.
we can encode Booleans and Natural Numbers using lambda calculus.
It was used by Alonzo Church to solve the Undecidability Problem a year before Alan Turing did!!