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:
“Unlike the normal pattern, I know I have grown more liberal as I’ve grown older. I have become more convinced that there is room for improvement in the world.”
—Walter Wellesley (Red)
“You may melt your metals and cast them into the most beautiful moulds you can; they will never excite me like the forms which this molten earth flows out into. And not only it, but the institutions upon it are plastic like clay in the hands of the potter.”
—Henry David Thoreau (1817–1862)