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:
“Like sleep disturbances, some worries at separation can be expected in the second year. If you accept this, then you will avoid reacting to this anxiety as if it’s your fault. A mother who feels guilty will appear anxious to the child, as if to affirm the child’s anxiety. By contrast, a parent who understands that separation anxiety is normal is more likely to react in a way that soothes and reassures the child.”
—Cathy Rindner Tempelsman (20th century)
“While waiting to get married, several forms of employment were acceptable. Teaching kindergarten was for those girls who stayed in school four years. The rest were secretaries, typists, file clerks, or receptionists in insurance firms or banks, preferably those owned or run by the family, but respectable enough if the boss was an upstanding Christian member of the community.”
—Barbara Howar (b. 1934)