Church-Rosser Theorem

Church-Rosser theorem

[¦chərch ¦rȯs·ər ¦thir·əm]
(mathematics)
If for a lambda expression there is a terminating reduction sequence yielding a reduced form B, then the leftmost reduction sequence will yield a reduced form that is equivalent to B up to renaming.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.

Church-Rosser Theorem

(theory)
A property of a reduction system that states that if an expression can be reduced by zero or more reduction steps to either expression M or expression N then there exists some other expression to which both M and N can be reduced. This implies that there is a unique normal form for any expression since M and N cannot be different normal forms because the theorem says they can be reduced to some other expression and normal forms are irreducible by definition. It does not imply that a normal form is reachable, only that if reduction terminates it will reach a unique normal form.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
The Church-Rosser theorem is a celebrated metamathematical result on the lambda calculus.