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:
“Literature is a defense against the attacks of life. It says to life: “You can’t deceive me. I know your habits, foresee and enjoy watching all your reactions, and steal your secret by involving you in cunning obstructions that halt your normal flow.””
—Cesare Pavese (1908–1950)
“Pervading nationalism imposes its dominion on man today in many different forms and with an aggressiveness that spares no one.... The challenge that is already with us is the temptation to accept as true freedom what in reality is only a new form of slavery.”
—Pope John Paul II (b. 1920)