Some of the things I've learned every day since Oct 10, 2016
50: Normalization Property (Lambda Calculus)
November 29, 2016Posted by on
In a rewrite system, such as -reduction in the lambda calculus, a term may or may not satisfy either the weak normalization or the strong normalization property.
A term satisfies the weak normalization property if there exists a sequence of rewrites on that eventually results in a normal form of : a term which is irreducible.
A term satisfies the strong normalization property if every sequence of rewrites on eventually results in a normal form of .
If every term in a rewrite system satisfies the [weak | strong] normalization property, then the system itself is said to satisfy the same property.
An example of a system which satisfies neither of the normalization properties is the pure untyped lambda calculus. An example of a non-normal term within this system is
Under -reduction, this term reduces to itself, and so it never terminates in an irreducible form.
Conversely, a term within this system which is weakly normal is
Under -reduction, this term reduces to just the variable , an irreducible term.
There are other forms of the lambda calculus, as well as other similar systems, which are normal. These can be viewed as programming languages in which every program eventually will (or can) terminate. A significant drawback to such a system, however, is that if a system is normal it cannot be Turing complete.
Additionally, in the lambda calculus every normalizing term has a unique normal form.