Computer Dictionary Online

Medical Dictionary   Law Dictionary   Legal Dictionary   Website Design

0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z 


Church-Rosser Theorem

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.

(1995-01-25)


Contact the Computer Dictionary Online  ::  Link to the Computer Dictionary Online  ::  Disclaimer for Computer Dictionary Online

Computer Dictionary Online
Copyright © 2017