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:
“I shouldn’t say I’m looking forward to leading a normal life, because I don’t know what normal is. This has been normal for me.”
—Martina Navratilova (b. 1956)
“The Dada object reflected an ironic posture before the consecrated forms of art. The surrealist object differs significantly in this respect. It stands for a mysterious relationship with the outer world established by man’s sensibility in a way that involves concrete forms in projecting the artist’s inner model.”
—J.H. Matthews. “Object Lessons,” The Imagery of Surrealism, Syracuse University Press (1977)