\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \)
deepdream of a sidewalk
Show Answer
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)
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 [...].