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:
“You will be again as normal and selfish and heartless as anybody
else.”
—Louise Bogan (18971970)
“A strange effect of marriage, such as the nineteenth century has made it! The boredom of married life inevitably destroys love, when love has preceded marriage. And yet, as a philosopher has observed, it speedily brings about, among people who are rich enough not to have to work, an intense boredom with all quiet forms of enjoyment. And it is only dried up hearts, among women, that it does not predispose to love.”
—Stendhal [Marie Henri Beyle] (17831842)