View source for Church–Rosser theorem

In [[mathematics]] and [[theoretical computer science]], the '''Church–Rosser theorem''' states that, when applying reduction rules to terms in the [[lambda calculus]], the ordering in which the reductions are chosen does not make a difference to the eventual result.

== Description ==

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]] and J. Barkley Rosser, after whom it is named.

== Diagram ==

(TO DO: diagram.)

The theorem is symbolized by the diagram at right [TO DO: add 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, the Church–Rosser theorem states that the reduction rules of the lambda calculus are confluent.

As a consequence of the theorem, a term in the lambda calculus has at most one normal form, justifying reference to "the normal form" of a given term.

== Holds for many variants of lambda calculus ==

The Church–Rosser theorem also holds for many variants of the lambda calculus, such as the simply-typed lambda calculus, many calculi with advanced type systems, and Gordon Plotkin's beta-value calculus.

Plotkin also used a Church–Rosser theorem to prove that the evaluation of [[Functional programming|functional programs]] (for both [[lazy evaluation]] and [[eager evaluation]]) is a function from programs to values (a subset of the lambda terms).

== In older research papers ==

In older research papers, a rewriting system is said to be Church–Rosser, or to have the Church–Rosser property, when it is confluent.

== See also ==

* [[Alonzo Church]]
* [[Functional programming]]
* [[Lambda calculus]]
* [[Mathematics]]
* [[Theoretical computer science]]

== External links == 

* [https://en.wikipedia.org/wiki/Church%E2%80%93Rosser_theorem Church–Rosser theorem] @ Wikipedia

[[Category:Computation]]
[[Category:Mathematics]]