Normal Forms and Confluence
For the untyped lambda calculus, β-reduction as a rewriting rule is neither strongly normalising nor weakly normalising.
However, it can be shown that β-reduction is confluent. (Of course, we are working up to α-conversion, i.e. we consider two normal forms to be equal, if it is possible to α-convert one into the other.)
Therefore, both strongly normalising terms and weakly normalising terms have a unique normal form. For strongly normalising terms, any reduction strategy is guaranteed to yield the normal form, whereas for weakly normalising terms, some reduction strategies may fail to find it.
Read more about this topic: Lambda Calculus
Famous quotes containing the words normal and/or forms:
“The word career is a divisive word. It’s a word that divides the normal life from business or professional life.”
—Grace Paley (b. 1922)
“One way to think about play, is as the process of finding new combinations for known things—combinations that may yield new forms of expression, new inventions, new discoveries, and new solutions....It’s exactly what children’s play seems to be about and explains why so many people have come to think that children’s play is so important a part of childhood—and beyond.”
—Fred Rogers (20th century)