Forma normal beta

De Viquipèdia
Salta a la navegació Salta a la cerca

En càlcul lambda, un terme està en forma normal beta si no és possible fer cap reducció beta.[1] Un terme està en forma normal beta-eta si no són possibles ni una reducció beta ni una reducció eta. Un terme està en forma normal de capçalera si no hi ha cap beta-redex en posició de capçalera.

Reducció beta[modifica]

En càlcul lambda, una beta redex[nota 1] és un terme de la forma

on és un terme depenent, possiblement, de la variable .

Una reducció beta és una aplicació de la següent regla de reescriptura a una beta redex:

on és el resultat de substituir la variable pel terme al terme .

Una reducció beta està en posició de capçalera si està en la forma següent:

, on .

Qualsevol reducció que no estigui en aquesta forma és una reducció beta interna.

Estratègies de reducció[modifica]

En general, pot haver-hi diferents reduccions beta possibles per a un terme donat. La reducció en ordre normal és l'estratègia d'avaluació en la qual hom continua aplicant la regla de reducció beta en posició inicial fins que no es pugui reduir més. Un cop arribat a aquest punt, el terme resultant està en forma normal.

En canvi, en una reducció en ordre aplicatiu hom aplica primer les reduccions internes i, quan ja no s'hi poden aplicar més, després s'aplica la reducció a la capçalera.

La reducció en ordre normal és completa, en el sentit que, si un terme té a la capçalera una forma normal, la reducció en ordre normal arribarà algun cop a aquesta capçalera. En canvi, pot ser que la reducció en ordre aplicatiu no acabi mai, fins i tot quan el terme té una forma normal. Per exemple, si hom usa una reducció en ordre aplicatiu, podem tenir aquesta successió de reduccions:

Però si hom usa les reduccions en ordre normal, l'expressió inicial es redueix ràpidament a una forma normal:

Les cadenes directrius de Sinot proporcionen un mètode per optimitzar la complexitat computacional de la reducció beta.

Notes[modifica]

  1. De l'anglès reducible expression, expressió reductible

Referències[modifica]

  1. «Beta normal form». Encyclopedia. TheFreeDictionary.com. [Consulta: 18 novembre 2013].

Vegeu també[modifica]