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:
“When a man says that he is Jesus or Napoleon, or that the Martians are after him, or claims something else that seems outrageous to common sense, he is labeled psychotic and locked up in a madhouse. Freedom of speech is only for normal people.”
—Thomas Szasz (b. 1920)
“Of the three forms of pride, that is to say pride proper, vanity, and conceit, vanity is by far the most harmless, and conceit by far the most dangerous. The meaning of vanity is to think too much of our bodily advantages, whether real or unreal, over others; while the meaning of conceit is to believe we are cleverer, wiser, grander, and more important than we really are.”
—John Cowper Powys (1872–1963)