Lambda calculus can be used to define (1) what a computable function is. The question of whether two lambda calculus expressions are equivalent cannot be solved by a general algorithm. This was the first question, even before the (2) halting problem for which undecidability could be proved.
Lambda calculus can be called the smallest universal programming language. It consists of a single
(1)transformation rule -----variable substitution
(2) function definition scheme.
Lambda calculus is universal in the sense that any computable function can be expressed and evaluated using this formalism. It is thus equivalent to the Turning Machine formalism.
Lambda calculus emphasizes the use of transformation rules(variable substitution) and does not care about the actual machine implementing them. It is an approach more related to software than to hardware.
No comments:
Post a Comment