Beta normal form

I lambdakalkylen är en term i betanormalform om ingen beta-reduktion är möjlig. En term är i beta-eta-normalform om varken en beta-reduktion eller en eta-reduktion är möjlig. En term är i normal form om det inte finns någon beta-redex i huvudposition .

Beta-reduktion

I lambdakalkylen är en beta redex en term av formen:

$(\mathbf {\lambda } xA)M$ .

En redex $r$ är i huvudposition i en term $t$ , om $t$ har följande form (observera att applikation har högre prioritet än abstraktion, och att formeln nedan är avsedd att vara en lambda-abstraktion, inte en applikation):

$\lambda x_{1}\ldots \lambda x_{n}.\underbrace {(\lambda xA)M_{1}} _{ {\text{the redex }}r}M_{2}\ldots M_{m}$ , där $n\geq 0$ och $m\geq 1$ .

En beta-reduktion är en tillämpning av följande omskrivningsregel på en beta-redex som ingår i en term:

$(\mathbf {\lambda } xA)M\longrightarrow A[x:=M]$

där $A[x:=M]$ är resultatet av att termen ${\displaystyle M} ersätts$ med variabeln $x$ i termen $A$ .

En betaminskning av huvudet är en betaminskning som tillämpas i huvudposition, det vill säga av följande form:

${\displaystyle \lambda x_{1}\ldots \lambda x_{n}.(\lambda xA)M_{1}M_{2}\ldots M_{m} \longrightarrow \lambda x_{1}\ldots \lambda x_{n}.A[x:=M_{1}]M_{2}\ldots M_{m}} , där n ≥ {\displaystyle n$ \ $n\geq 0$ and $m\geq 1$.

Varje annan minskning är en intern beta-reduktion.

En normalform är en term som inte innehåller något beta redex, dvs som inte kan reduceras ytterligare. En huvudnormalform är en term som inte innehåller ett beta-redex i huvudläge, dvs som inte kan reduceras ytterligare genom en huvudreduktion. När man överväger den enkla lambdakalkylen (dvs utan tillägg av konstant- eller funktionssymboler, avsedda att reduceras med ytterligare deltaregel), är huvudnormala former termerna för följande form:

${\displaystyle \lambda x_{1}\ldots \lambda x_{n}.xM_{1}M_{2}\ldots M_{m}} ,$ där $x$ är en variabel, $n\geq 0$ och $m\geq 0$ .

En huvudnormalform är inte alltid en normalform, eftersom de tillämpade argumenten $M_{j}$ inte behöver vara normala. Men det omvända är sant: vilken normal form som helst är också en huvudnormalform. I själva verket är normalformerna exakt huvudnormalformerna där undertermerna $M_{j}$ i sig är normala former. Detta ger en induktiv syntaktisk beskrivning av normala former.

Det finns också begreppet svagt huvud normal form : en term i svag huvud normal form är antingen en term i huvud normal form eller en lambda abstraktion. Detta betyder att ett redex kan dyka upp inuti en lambdakropp.

Reduktionsstrategier

I allmänhet kan en given term innehålla flera redoxer, därför kan flera olika beta-reduktioner tillämpas. Vi kan specificera en strategi för att välja vilken redex som ska minskas.

• Normalordningsreduktion är strategin där man kontinuerligt tillämpar regeln för beta-reduktion i huvudposition tills inga fler sådana minskningar är möjliga. Vid den tidpunkten är den resulterande termen i normal form. Man fortsätter sedan att tillämpa huvudreduktion i undertermerna ${\displaystyle M_{j}} ,$ från vänster till höger. Med andra ord är normalordningsreduktion den strategi som alltid reducerar den yttersta vänstra redexen först.
• Däremot, i applicerande ordningsreduktion tillämpar man de interna minskningarna först, och tillämpar sedan endast huvudreduktionen när inga fler interna minskningar är möjliga.

Normalordningsreduktion är komplett, i den meningen att om en term har en huvudnormalform, så kommer normalordningsreduktion så småningom att nå den. Genom den syntaktiska beskrivningen av normalformer ovan innebär detta samma uttalande för en "helt" normalform (detta är standardiseringssatsen). Tillämplig orderreduktion får däremot inte upphöra, även när termen har en normal form. Om du till exempel använder applicerande orderreduktion är följande sekvens av reduktioner möjlig:

${\ displaystyle {\begin{aligned}&(\mathbf {\lambda } xz)((\lambda w.www)(\lambda w.www))\\\rightarrow &(\lambda xz)((\lambda w.www) )(\lambda w.www)(\lambda w.www))\\\högerpil &(\lambda xz)((\lambda w.www)(\lambda w.www)(\lambda w.www)(\ lambda w.www))\\\högerpil &(\lambda xz)((\lambda w.www)(\lambda w.www)(\lambda w.www)(\lambda w.www)(\lambda w.www. www))\\&\ldots \end{aligned}}}$

Men med normal ordningsreduktion reduceras samma utgångspunkt snabbt till normal form:

$(\mathbf {\lambda } xz)((\lambda w.www)(\lambda w.www) ))$

$\rightarrow z$

Sinots regissörssträngar är en metod med vilken beta-reduktionens beräkningskomplexitet kan optimeras.

Se även

• Lambdakalkyl
• Normalform (disambiguation)