Math and science::Theory of Computation::Lambda calculus

β-normal form

β-normal form

Let $$M$$ be a lambda term.

• $$M$$ is said to be in β-normal form iff [...].
• $$M$$ is said to have a β-normal form iff [...].

The definition of redex is recalled on back side.

The notion of β-normal form captures a sense of the result of a lambda term; from a β-normal form, no further lambda computation is possible.

The following definition elaborates the concept by considering how many normal forms a term might have.

Weakly normalizing and strongly normalizing

Let $$M$$ be a lambda term.

• $$M$$ is said to be weakly normalizing iff it [...].
• $$M$$ is said to be strongly normalizing iff there are no [...].