LambdaKalküls

The LambdaKalküls, commonly known in English as the lambda calculus, is a formal system in mathematical logic and computer science that models computation through function abstraction and application. It provides a minimal framework for defining and transforming computable expressions and serves as a foundational model for functional programming languages.

Its syntax consists of three elements: variables, abstraction (λx. M), and application (M N). A term can be reduced by beta-reduction, where an application of an abstraction is replaced by the body with the bound variable substituted. Alpha-conversion allows renaming bound variables to avoid clashes, and eta-conversion expresses extensional equality, though η is optional in many variants.

Two main variants exist: untyped lambda calculus, which is highly expressive and may not terminate, and typed lambda calculus, which introduces a type system to constrain terms and often guarantees termination. Data and data operations can be encoded using pure functions, such as Church numerals and Church booleans.

LambdaKalküls is computationally universal: every computable function can be represented as a lambda-term, and, conversely, lambda terms can be simulated by a Turing machine. This equivalence underpins the Church-Turing thesis. The calculus influenced the design of functional programming languages like Haskell, Scheme, and OCaml in their core semantics.

History and influence: Introduced in the 1930s by Alonzo Church, the lambda calculus has since become a central tool in formal semantics, type theory, and compiler design. It remains a standard subject in theoretical computer science and logic.