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:
“Perhaps the feelings that we experience when we are in love represent a normal state. Being in love shows a person who he should be.”
—Anton Pavlovich Chekhov (1860–1904)
“All ... forms of consensus about “great” books and “perennial” problems, once stabilized, tend to deteriorate eventually into something philistine. The real life of the mind is always at the frontiers of “what is already known.” Those great books don’t only need custodians and transmitters. To stay alive, they also need adversaries. The most interesting ideas are heresies.”
—Susan Sontag (b. 1933)