lambdakalkyle

Lambdakalkyle, or lambda calculus, is a formal system in mathematical logic and computer science for expressing computation based on function abstraction and application. It was introduced by Alonzo Church in the 1930s as a framework for studying computability and the foundations of mathematics. The core idea is to build expressions using variables, lambda abstractions, and function application, and to compute by applying functions to arguments.

The syntax consists of three kinds of terms: variables, abstractions written as lambda x. M, and applications written as (M N). A lambda abstraction represents a function, and application represents function execution. Variables may be bound by abstractions; free and bound occurrences are distinguished, and alpha-conversion allows renaming bound variables to avoid name capture. Substitution replaces bound variables with terms during beta-reduction, the primary computation rule.

Beta-reduction expresses computation: (λx. M) N reduces to M[x := N]. Repeated beta-reduction transforms expressions toward a normal form. In some variants, eta-conversion expresses extensional equivalence, such as λx. (f x) ≡ f when x is not free in f. The untyped lambda calculus has no restriction on terms and can express non-terminating computations, while typed variants restrict forms to guarantee termination in many cases.

Variants and significance: simply typed lambda calculus introduces a type system; more advanced systems include polymorphic and dependent types, with the Curry-Howard correspondence linking types to logic. Lambda calculus can encode booleans, numbers, and data structures via Church encodings, illustrating its expressive power. It is foundational to the theory of programming languages and has influenced the design of functional languages such as Lisp, Scheme, Haskell, and OCaml. It is also known to be Turing complete, equivalent in expressive power to Turing machines under the Church-Turing thesis.