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:
“Separation anxiety is normal part of development, but individual reactions are partly explained by experience, that is, by how frequently children have been left in the care of others.... A mother who is never apart from her young child may be saying to him or her subliminally: “You are only safe when I’m with you.””
—Cathy Rindner Tempelsman (20th century)
“The time will come when the evil forms we have known can no more be organized. Man’s culture can spare nothing, wants all material. He is to convert all impediments into instruments, all enemies into power.”
—Ralph Waldo Emerson (1803–1882)