Search in: Word
Vietnamese keyboard: Off
Virtual keyboard: Show
Computing (FOLDOC) dictionary
Church-Rosser Theorem
Jump to user comments
This property of a reduction system 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.