CHURCH-ROSSER THEOREM
\t͡ʃˈɜːt͡ʃɹˈɒsə θˈi͡əɹəm], \tʃˈɜːtʃɹˈɒsə θˈiəɹəm], \tʃ_ˈɜː_tʃ_ɹ_ˈɒ_s_ə θ_ˈiə_ɹ_ə_m]\
Sort: Oldest first
-
A property of a reduction system that states thatif an expression can be reduced by zero or more reductionsteps to either expression M or expression N then there existssome other expression to which both M and N can be reduced.This implies that there is a unique normal form for anyexpression since M and N cannot be different normal formsbecause the theorem says they can be reduced to some otherexpression and normal forms are irreducible by definition. Itdoes not imply that a normal form is reachable, only that ifreduction terminates it will reach a unique normal form.
By Denis Howe
Nearby Words
- church-land
- church-living
- church-membership
- church-owl
- church-rate
- Church-Rosser Theorem
- church-state
- church-warden
- church-wardens
- church-way
- church-work