Lambda calculus or to express differently, λ-calculus formulated by famous American mathematician and logician Alonzo Church is a system of mathematical logic that played key role in the subsequent development of computer science. This mathematical system of logic made the computation based on function abstraction and variable and substitution based application possible. This system of mathematical logic is the first stepping stone towards conceptualization of effective computability in the path shown by Alonzo Church. Etymologically the name Lambda as given to this system of logic can be traced to Greek alphabet signifying binding of the variables in a logical function. This simple and universally accepted model of computation later has been contested by Turing machines in respect of expressiveness as shown by Alan Turing back in 1937.
Variants of Lambda calculus and development of computing theory
Notion of variable binding and substitution made this system of mathematical logic crucially too important for the development of computing and computing theories as a whole. In the subsequent time various systems born out of the core concept creating both typed and untyped variants of Lambda calculus. As for historical importance untyped variant of Lambda calculus is more important in contributing to the development of computing theories and mathematical models. In the untyped lambda calculus the function application experiences no restrictions and thus a situation emerges in which the domain of a particular function is not built into the system making the function free of domain specifications. In the time to come depending on this logic the basis of computing theory will be formulated in the Church-Turing theory where it would be claimed that the untyped variant of Lambda calculus can perform effectively all calculable functions. The typed variant of this computing logic restricts itself to application of function in which it depends upon the function to accept the given input (type) of data.
Importance and widespread applications
Lambda calculus is one of the major building blocks and milestones in the scientific progress of computing and mathematical theories and applications. Over the years the applications emanating from this system of computing logic spanned over diverse fields including computer science, mathematics, linguistics and philosophy. It still plays a vital role in the theory corresponding to computability besides Turing machines as another model of computation developed almost in the same period way back in 1930s. Lambda calculus is particularly important for its great role in the development of programming theory and programming language. Functional programming languages implementing the calculus improved by the constellation of constants and data types are considered as counterparts to Lambda calculus. Though programming languages and theory is still the greatest area of implementation of this system of computing and mathematical logic, it has also an array of applications in proof theory. The Curry-Howard correspondence can be cited as a model example of this type of applications in which we can see the correspondence between diverse systems of typed Lambda calculus and systems pertaining to formal logic.
Posted on: February 18, 2014 If you enjoyed this post then why not add us on Google+? Add us to your Circles