LambdaKalkül

LambdaKalkül is a formal system in mathematical logic and computer science for expressing computation based on function abstraction and application using variable binding and substitution. It was developed by Alonzo Church in the 1930s. The core idea is to represent all computable functions as lambda expressions.

A lambda expression consists of a variable, a lambda abstraction, or an application. A lambda abstraction is of the form λx.M, which represents a function that takes an argument x and returns the result of the expression M. An application is of the form M N, which represents applying the function M to the argument N.

The primary operation in LambdaKalkül is beta-reduction, which is the process of applying a function to its argument. If M is λx.B and N is an expression, then (λx.B) N reduces to B[x := N], where B[x := N] means substituting all free occurrences of x in B with N. Other reduction rules include alpha-conversion (renaming bound variables) and eta-conversion (removing redundant abstractions).

LambdaKalkül is a universal model of computation, meaning that any function that can be computed by a Turing machine can also be computed by a lambda expression. This universality has made it a foundational concept in theoretical computer science, particularly in the design of programming languages, functional programming, and the theory of computation. It provides a precise and abstract way to study computation without relying on specific hardware implementations.