Lambda calculus

• Report rights infringement
• published: 24 Jul 2014
• views: 2251

Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic and computer science for expressing computation based on function abstraction and application using variable binding and substitution. First formulated by Alonzo Church to formalize the concept of effective computability, lambda calculus found early successes in the area of computability theory, such as a negative answer to Hilbert's Entscheidungsproblem. Lambda calculus is a conceptually simple universal model of computation (Turing showed in 1937 that Turing machines equalled the lambda calculus in expressiveness). The name derives from the Greek letter lambda (λ) used to denote binding a variable in a function. Because of the importance of the notion of variable binding and substitution, there is not just one system of lambda calculus, and in particular there are typed and untyped variants. Historically, the most important system was the untyped lambda calculus, in which function application has no restrictions (so the notion of the domain of a function is not built into the system). In the Church–Turing Thesis, the untyped lambda calculus is claimed to be capable of computing all effectively calculable functions. The typed lambda calculus is a variety that restricts function application, so that functions can only be applied if they are capable of accepting the given input's "type" of data. This video is targeted to blind users. Attribution: Article text available under CC-BY-SA Creative Commons image source in video