Lambda Calculus - Normal Forms and Confluence

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:

    The basic thing nobody asks is why do people take drugs of any sort?... Why do we have these accessories to normal living to live? I mean, is there something wrong with society that’s making us so pressurized, that we cannot live without guarding ourselves against it?
    John Lennon (1940–1980)

    I may not tell
    of the forms that pass and pass,
    of that constant old, old face
    that leaps from each wave
    to wait underneath the boat
    in the hope that at last she’s lost.
    Hilda Doolittle (1886–1961)