In
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation th ...
, the Church–Rosser theorem states that, when applying
reduction rules to
term
Term may refer to:
* Terminology, or term, a noun or compound word used in a specific context, in particular:
**Technical term, part of the specialized vocabulary of a particular field, specifically:
***Scientific terminology, terms used by scient ...
s, the ordering in which the reductions are chosen does not make a difference to the eventual result.
More precisely, if there are two distinct reductions or sequences of reductions that can be applied to the same term, then there exists a term that is reachable from both results, by applying (possibly empty) sequences of additional reductions. The theorem was proved in 1936 by
Alonzo Church
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scien ...
and
J. Barkley Rosser, after whom it is named.
The theorem is symbolized by the adjacent diagram: If term ''a'' can be reduced to both ''b'' and ''c'', then there must be a further term ''d'' (possibly equal to either ''b'' or ''c'') to which both ''b'' and ''c'' can be reduced.
Viewing the lambda calculus as an
abstract rewriting system
In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviated ARS) is a formalism that captures the quintessential notion and properties of rewriting s ...
, the Church–Rosser theorem states that the reduction rules of the lambda calculus are
confluent
In geography, a confluence (also: ''conflux'') occurs where two or more flowing bodies of water join to form a single channel. A confluence can occur in several configurations: at the point where a tributary joins a larger river (main stem); o ...
. As a consequence of the theorem, a term in the
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation th ...
has at most one
normal form, justifying reference to "''the'' normal form" of a given normalizable term.
History
In 1936,
Alonzo Church
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scien ...
and
J. Barkley Rosser proved that the theorem holds for β-reduction in the λI-calculus (in which every abstracted variable must appear in the term's body). The proof method is known as "finiteness of developments", and it has additional consequences such as the Standardization Theorem, which relates to a method in which reductions can be performed from left to right to reach a normal form (if one exists). The result for the pure untyped lambda calculus was proved by D. E. Shroer in 1965.
Pure untyped lambda calculus
One type of reduction in the pure untyped lambda calculus for which the Church–Rosser theorem applies is β-reduction, in which a subterm of the form
is contracted by the substitution