Forme normale (réécriture abstraite)

Dans la réécriture abstraite , un objet est sous forme normale s'il ne peut plus être réécrit, c'est-à-dire s'il est irréductible. Selon le système de réécriture, un objet peut être réécrit sous plusieurs formes normales ou aucune. De nombreuses propriétés des systèmes de réécriture se rapportent aux formes normales.

Définitions

Formellement, si ( A ,→) est un système de réécriture abstrait , x ∈ A est sous forme normale si aucun y ∈ A n'existe tel que x → y , c'est-à-dire que x est un terme irréductible.

Un objet a est faiblement normalisant s'il existe au moins une séquence particulière de réécritures commençant par a qui donne finalement une forme normale. Un système de réécriture a la propriété de normalisation faible ou est (faiblement) normalisant (WN) si chaque objet est faiblement normalisant. Un objet a est fortement normalisant si chaque séquence de réécritures commençant par a se termine finalement par une forme normale. Un système de réécriture abstrait est fortement normalisant , terminus , noethérien ou a la propriété de normalisation (forte) (SN), si chacun de ses objets est fortement normalisant.

Un système de réécriture possède la propriété de forme normale (NF) si pour tous les objets a et les formes normales b , b peut être atteint à partir de a par une série de réécritures et de réécritures inverses seulement si a se réduit à b . Un système de réécriture possède la propriété de forme normale unique (UN) si pour toutes les formes normales a , b ∈ S , a peut être atteint à partir de b par une série de réécritures et de réécritures inverses seulement si a est égal à b . Un système de réécriture possède la propriété de forme normale unique par rapport à la réduction (UN ^→ ) si pour tout terme se réduisant aux formes normales a et b , a est égal à b .

Résultats

Cette section présente quelques résultats bien connus. Tout d'abord, SN implique WN.

Confluence (abrégé CR) implique NF implique UN implique UN ^→ . Les implications inverses ne sont généralement pas valables. {a→b,a→c,c→c,d→c,d→e} est UN ^→ mais pas UN car b=e et b,e sont des formes normales. {a→b,a→c,b→b} est UN mais pas NF car b=c, c est une forme normale et b ne se réduit pas à c. {a→b,a→c,b→b,c→c} est NF car il n'y a pas de formes normales, mais pas CR car a se réduit à b et c, et b,c n'ont pas de réduction commune.

WN et UN ^→ impliquent une confluence. Par conséquent, CR, NF, UN et UN ^→ coïncident si WN est vrai.

Exemples

Un exemple est que la simplification des expressions arithmétiques produit un nombre - en arithmétique, tous les nombres sont des formes normales. Un fait remarquable est que toutes les expressions arithmétiques ont une valeur unique, donc le système de réécriture est fortement normalisant et confluent :

(3 + 5) * (1 + 2) ⇒ 8 * (1 + 2) ⇒ 8 * 3 ⇒ 24

(3 + 5) * (1 + 2) ⇒ (3 + 5) * 3 ⇒ 3*3 + 5*3 ⇒ 9 + 5*3 ⇒ 9 + 15 ⇒ 24

Des exemples de systèmes non normalisants (ni faiblement ni fortement) incluent le comptage jusqu'à l'infini (1 ⇒ 2 ⇒ 3 ⇒ ...) et des boucles telles que la fonction de transformation de la conjecture de Collatz (1 ⇒ 2 ⇒ 4 ⇒ 1 ⇒ ..., c'est un problème ouvert s'il existe d'autres boucles de la transformation de Collatz). Un autre exemple est le système à règle unique { r ( x , y ) → r ( y , x ) }, qui n'a pas de propriétés normalisantes puisque à partir de n'importe quel terme, par exemple r (4,2) une seule séquence de réécriture démarre, à savoir r (4,2) → r (2,4) → r (4,2) → r (2,4) → ..., qui est infiniment long. Cela conduit à l'idée de réécrire « modulo la commutativité », où un terme est sous forme normale si aucune règle autre que la commutativité ne s'applique.

Le système { b → a , b → c , c → b , c → d } (illustré) est un exemple de système faiblement normalisant mais pas fortement normalisant. a et d sont des formes normales, et b et c peuvent être réduits à a ou d , mais la réduction infinie b → c → b → c → ... signifie que ni b ni c ne sont fortement normalisants.

Calcul lambda non typé

Le calcul lambda pur non typé ne satisfait pas la propriété de normalisation forte, ni même la propriété de normalisation faible. Considérons le terme (l'application est associative à gauche ). Il a la règle de réécriture suivante : Pour tout terme , ${\displaystyle \lambda x.xxx <semantics> <mrow> <mstyle> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> </mstyle> </mrow> <annotation>{\displaystyle \lambda x.xxx}</annotation> </semantics> </math></span><img src=$ ${\displaystyle t <semantics> <mrow> <mstyle> <mi>t</mi> </mstyle> </mrow> <annotation>{\displaystyle t}</annotation> </semantics> </math></span><img src=$

{\displaystyle (\mathbf {\lambda } x.xxx)t ightarrow ttt <semantics> <mrow> <mstyle> <mo>(</mo> <mrow> <mi>λ</mi> </mrow> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mi>t</mi> <mo>→</mo> <mi>t</mi> <mi>t</mi> <mi>t</mi> </mstyle> </mrow> <annotation>{\displaystyle (\mathbf {\lambda } x.xxx)t ightarrow ttt}</annotation> </semantics> </math></span><img src=

Mais considérons ce qui se passe lorsque nous l'appliquons à lui-même : ${\displaystyle \lambda x.xxx <semantics> <mrow> <mstyle> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> </mstyle> </mrow> <annotation>{\displaystyle \lambda x.xxx}</annotation> </semantics> </math></span><img src=$

{\displaystyle {\begin{aligned}(\mathbf {\lambda } x.xxx)(\lambda x.xxx)& ightarrow (\mathbf {\lambda } x.xxx)(\lambda x.xxx)(\lambda x.xxx)\\& ightarrow (\mathbf {\lambda } x.xxx)(\lambda x.xxx)(\lambda x.xxx)(\lambda x.xxx)\\& ightarrow (\mathbf {\lambda } x.xxx)(\lambda x.xxx)(\lambda x.xxx)(\lambda x.xxx)(\lambda x.xxx)\\& ightarrow \ \cdots \,\end{aligned <semantics> <mrow> <mstyle> <mrow> <mtable> <mtr> <mtd> <mo>(</mo> <mrow> <mi>λ</mi> </mrow> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> </mtd> <mtd> <mi></mi> <mo>→</mo> <mo>(</mo> <mrow> <mi>λ</mi> </mrow> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>→</mo> <mo>(</mo> <mrow> <mi>λ</mi> </mrow> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>→</mo> <mo>(</mo> <mrow> <mi>λ</mi> </mrow> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>→</mo> <mtext> </mtext> <mo>⋯</mo> <mspace></mspace> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\begin{aligned}(\mathbf {\lambda } x.xxx)(\lambda x.xxx)& ightarrow (\mathbf {\lambda } x.xxx)(\lambda x.xxx)(\lambda x.xxx)\\& ightarrow (\mathbf {\lambda } x.xxx)(\lambda x.xxx)(\lambda x.xxx)(\lambda x.xxx)\\& ightarrow (\mathbf {\lambda } x.xxx)(\lambda x.xxx)(\lambda x.xxx)(\lambda x.xxx)(\lambda x.xxx)\\& ightarrow \ \cdots \,\end{aligned}}}</annotation> </semantics> </math></span><img src=

Par conséquent, le terme n'est pas fortement normalisant. Et c'est la seule séquence de réduction, donc il n'est pas non plus faiblement normalisant. ${\displaystyle (\lambda x.xxx)(\lambda x.xxx) <semantics> <mrow> <mstyle> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> <mo>(</mo> <mi>λ</mi> <mi>x</mi> <mo>.</mo> <mi>x</mi> <mi>x</mi> <mi>x</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle (\lambda x.xxx)(\lambda x.xxx)}</annotation> </semantics> </math></span><img src=$

Calcul lambda typé

Différents systèmes de calcul lambda typé, dont le calcul lambda simplement typé , le système F de Jean-Yves Girard et le calcul des constructions de Thierry Coquand, sont fortement normalisants.

Un système de calcul lambda avec la propriété de normalisation peut être considéré comme un langage de programmation avec la propriété que chaque programme se termine . Bien que cette propriété soit très utile, elle présente un inconvénient : un langage de programmation avec la propriété de normalisation ne peut pas être Turing-complet , sinon on pourrait résoudre le problème d'arrêt en vérifiant si le type du programme est vérifié. Cela signifie qu'il existe des fonctions calculables qui ne peuvent pas être définies dans le calcul lambda simplement typé, et de même pour le calcul des constructions et le système F. Un exemple typique est celui d'un auto-interpréteur dans un langage de programmation total .