Hiérarchie de Grzegorczyk - Grzegorczyk hierarchy

La hiérarchie Grzegorczyk ( / ɡ r ɛ ɡ ɔːr tʃ ə k / , prononciation polonaise:  [ɡʐɛɡɔrt͡ʂɨk] ), du nom du logicien polonais Andrzej Grzegorczyk , une hiérarchie des fonctions utilisées dans la théorie de la calculabilité (Wagner et Wechsung 1986: 43). Chaque fonction de la hiérarchie de Grzegorczyk est une fonction récursive primitive et chaque fonction récursive primitive apparaît dans la hiérarchie à un certain niveau. La hiérarchie traite de la vitesse à laquelle les valeurs des fonctions croissent ; intuitivement, les fonctions des niveaux inférieurs de la hiérarchie se développent plus lentement que les fonctions des niveaux supérieurs.

Définition

Nous introduisons d'abord un ensemble infini de fonctions, noté E _i pour un nombre naturel i . Nous définissons et . C'est-à-dire que E ₀ est la fonction d'addition, et E ₁ est une fonction unaire qui met au carré son argument et en ajoute deux. Ensuite, pour chaque n supérieur à 2, on définit , c'est-à-dire le x- ième itéré de évalué à 2. ${\style d'affichage E_{0}(x,y)=x+y}$${\displaystyle E_{1}(x)=x^{2}+2}$${\displaystyle E_{n}(x)=E_{n-1}^{x}(2)}$${\style d'affichage E_{n-1}}$

A partir de ces fonctions, nous définissons la hiérarchie de Grzegorczyk. , le n- ième ensemble dans la hiérarchie, contient les fonctions suivantes : ${\displaystyle {\mathcal {E}}^{n}}$

1. E _k pour k < n
2. la fonction zéro ( Z ( x ) = 0);
3. la fonction successeur ( S ( x ) = x + 1);
4. les fonctions de projection ( ) ;${\displaystyle p_{i}^{m}(t_{1},t_{2},\dots ,t_{m})=t_{i}}$
5. les compositions (généralisées) des fonctions dans l'ensemble (si h , g ₁ , g ₂ , ... et g _m sont dans , alors l' est aussi); et${\displaystyle {\mathcal {E}}^{n}}$${\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m }({\bar {u}}))}$
6. les résultats de la récursivité (primitive) limitée appliquée aux fonctions de l'ensemble, (si g , h et j sont dans et pour tout t et , et plus loin et , alors f est aussi dans )${\displaystyle {\mathcal {E}}^{n}}$${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$${\displaystyle {\bar {u}}}$${\displaystyle f(0,{\bar {u}})=g({\bar {u}})}$${\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}$${\displaystyle {\mathcal {E}}^{n}}$

En d'autres termes, c'est la fermeture de l'ensemble par rapport à la composition des fonctions et à la récursivité limitée (comme défini ci-dessus). ${\displaystyle {\mathcal {E}}^{n}}$${\displaystyle B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}}$

Propriétés

Ces ensembles forment clairement la hiérarchie

${\displaystyle {\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots }$

car ce sont des fermetures sur les et . ${\style d'affichage B_{n}}$${\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots }$

Ce sont des sous-ensembles stricts (Rose 1984; Gakwaya 1997). Autrement dit

${\displaystyle {\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots }$

parce que l' hyper opération est dans mais pas dans . ${\style d'affichage H_{n}}$${\displaystyle {\mathcal {E}}^{n}}$${\displaystyle {\mathcal {E}}^{n-1}}$

• ${\displaystyle {\mathcal {E}}^{0}}$inclut des fonctions telles que x +1, x +2, ...
• ${\displaystyle {\mathcal {E}}^{1}}$fournit toutes les fonctions d'addition, telles que x + y , 4 x , ...
• ${\displaystyle {\mathcal {E}}^{2}}$fournit toutes les fonctions de multiplication, telles que xy , x ⁴
• ${\displaystyle {\mathcal {E}}^{3}}$fournit toutes les fonctions d'exponentiation, telles que x ^y , 2 ^{2 2 x} , et est exactement les fonctions récursives élémentaires .
• ${\displaystyle {\mathcal {E}}^{4}}$fournit toutes les fonctions de tétration , et ainsi de suite.

Notamment, la fonction et la fonction caractéristique du prédicat du théorème de la forme normale de Kleene sont définissables de telle sorte qu'elles se situent au niveau de la hiérarchie de Grzegorczyk. Cela implique en particulier que tout ensemble récursivement énumérable est énumérable par une -fonction. ${\style d'affichage U}$${\style d'affichage T}$${\displaystyle {\mathcal {E}}^{0}}$${\displaystyle {\mathcal {E}}^{0}}$

Relation avec les fonctions récursives primitives

La définition de est la même que celle des fonctions récursives primitives , PR , sauf que la récursivité est limitée ( pour certains j in ) et que les fonctions sont explicitement incluses dans . Ainsi, la hiérarchie de Grzegorczyk peut être considérée comme un moyen de limiter le pouvoir de récursivité primitive à différents niveaux. ${\displaystyle {\mathcal {E}}^{n}}$${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$${\displaystyle {\mathcal {E}}^{n}}$${\style d'affichage (E_{k})_{k<n}}$${\displaystyle {\mathcal {E}}^{n}}$

Il ressort de ce fait que toutes les fonctions à n'importe quel niveau de la hiérarchie de Grzegorczyk sont des fonctions récursives primitives (c'est-à-dire ) et donc : ${\displaystyle {\mathcal {E}}^{n}\subseteq {\mathsf {PR}}}$

${\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}\subseteq {\mathsf {PR}}}$

On peut également montrer que toutes les fonctions récursives primitives sont à un certain niveau de la hiérarchie (Rose 1984; Gakwaya 1997), ainsi

${\displaystyle \bigcup _{n}{{\mathcal {E}}^{n}}={\mathsf {PR}}}$

et les ensembles partitionnent l'ensemble des fonctions récursives primitives PR . ${\displaystyle {\mathcal {E}}^{0},{\mathcal {E}}^{1}-{\mathcal {E}}^{0},{\mathcal {E}}^{2} -{\mathcal {E}}^{1},\dots ,{\mathcal {E}}^{n}-{\mathcal {E}}^{n-1},\dots }$

Rallonges

La hiérarchie de Grzegorczyk peut être étendue aux ordinaux transfinis . De telles extensions définissent une hiérarchie à croissance rapide . Pour ce faire, les fonctions génératrices doivent être définies récursivement pour les ordinaux limites (notez qu'elles ont déjà été définies récursivement pour les ordinaux successeurs par la relation ). S'il existe une manière standard de définir une suite fondamentale , dont l' ordinal limite est , alors les fonctions génératrices peuvent être définies . Cependant, cette définition dépend d'une manière standard de définir la séquence fondamentale. Rose (1984) propose une méthode standard pour tous les ordinaux α < ε ₀ . ${\displaystyle E_{\alpha }}$${\displaystyle E_{\alpha +1}(n)=E_{\alpha }^{n}(2)}$ ${\displaystyle \lambda _{m}}$${\style d'affichage \lambda }$${\displaystyle E_{\lambda }(n)=E_{\lambda _{n}}(n)}$

L'extension originale était due à Martin Löb et Stan S. Wainer (1970) et est parfois appelée la hiérarchie Löb-Wainer .

Voir également

• ÉLÉMENTAIRE
• Analyse ordinale

Remarques

Les références

• Brainerd, WS, Landweber, LH (1974), Théorie du calcul , Wiley, ISBN  0-471-09585-0
• Cichon, EA ; Wainer, SS (1983), "La croissance lente et les hiérarchies de Grzegorczyk", Journal of Symbolic Logic , 48 (2) : 399-408, doi : 10.2307/2273557 , ISSN  0022-4812 , MR  0704094
• Gakwaya, J.-S. (1997), Une enquête sur la hiérarchie de Grzegorczyk et son extension à travers le modèle de calculabilité BSS
• Grzegorczyk, A (1953). « Certaines classes de fonctions récursives » (PDF) . Rozprawy matematyczne . 4 : 1–45.
• Löb, MH; Wainer, SS (1970). "Hiérarchies des Fonctions Théoriques des Nombres I, II: Une Correction". Archiv für mathematische Logik und Grundlagenforschung . 14 : 198-199. doi : 10.1007/bf01991855 .
• Rose, HE, Subrecursion: Functions and hierarchies , Oxford University Press, 1984. ISBN  0-19-853189-3
• Wagner, K. et Wechsung, G. (1986), Computational Complexity , Mathematics and its Applications v. 21. ISBN  978-90-277-2146-4