Lambdakalkul

Lambdakalkul, commonly known as the lambda calculus, is a formal system in mathematical logic and computer science used to study computation based on function abstraction and application. It was introduced in the 1930s by Alonzo Church as part of investigations into the foundations of mathematics and decision problems. The system provides a minimal and powerful framework for defining and applying functions using simple syntactic constructs.

Terms in the lambda calculus are built from variables, abstractions (lambda abstractions) and applications. An abstraction has the form λx. M, representing a function that takes an argument x and returns M. An application has the form MN, representing the process of applying function M to argument N. Computation proceeds through beta reduction, which rewrites (λx. M) N to M[x := N], substituting N for x in M. Eta reduction expresses a notion of function extensionality, allowing λx. (f x) to be simplified to f when x is not free in f. A term is in normal form when no beta reductions are possible.

The untyped lambda calculus allows any term and is Turing complete, meaning it can express all computable functions. It also enables encoding of data structures such as booleans and numbers (via Church encodings). Simply typed lambda calculus introduces a type system that guarantees termination and aligns with constructive logic (via the Curry–Howard correspondence). More expressive typed systems exist, including polymorphic and dependent types.

Lambda calculus is foundational to functional programming languages (such as Scheme, Lisp, and Haskell) and to formal semantics, program analysis, and compiler design. Related formalisms include combinatory logic (SKI calculus), which offers a variable-free alternative with equivalent expressive power. The lambda calculus and Turing machines are regarded as two equivalent models of computation in the Church–Turing framework.