Editing Church–Rosser theorem (section)

{{Short description|Theorem in theoretical computer science}}
[[Image:Confluence.svg|right|200px]]
In [[lambda calculus]], the '''Church–Rosser theorem''' states that, when applying [[Lambda calculus#Reduction|reduction rules]] to [[term (logic)|term]]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.{{sfnp|Alama|2017}} The theorem was proved in 1936 by [[Alonzo Church]] 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]], the Church–Rosser theorem states that the reduction rules of the lambda calculus are [[confluence (abstract rewriting)|confluent]].  As a consequence of the theorem, a term in the [[lambda calculus]] has at most one [[Beta normal form|normal form]], justifying reference to "''the'' normal form" of a given normalizable term.