Talk:Church–Rosser theorem
This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||
|
Distinct vs possibly empty sequence of reductions[edit]
We say, "The Church–Rosser theorem states that if there are two distinct reductions starting from the same lambda calculus term, then there exists a term that is reachable via a (possibly empty) sequence of reductions from both reducts."
If the reducts are distinct, how can there exist a term that is reachable by an empty sequence of reductions? — Matt Crypto 09:20, 26 September 2009 (UTC)
- What's the problem? Two distinct reductions could end at the same term. Or two reductions could end at terms a and b where b can be reduced to a by further reductions; then the common reachable term is a, and the reduction sequence from a is empty.