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:
“Philosophically, incest asks a fundamental question of our shifting mores: not simply what is normal and what is deviant, but whether such a thing as deviance exists at all in human relationships if they seem satisfactory to those who share them.”
—Elizabeth Janeway (b. 1913)
“Media mystifications should not obfuscate a simple, perceivable fact; Black teenage girls do not create poverty by having babies. Quite the contrary, they have babies at such a young age precisely because they are poor—because they do not have the opportunity to acquire an education, because meaningful, well-paying jobs and creative forms of recreation are not accessible to them ... because safe, effective forms of contraception are not available to them.”
—Angela Davis (b. 1944)