Hiérarchie de Grzegorczyk
La hiérarchie de Grzegorczyk – du nom du logicien polonais Andrzej Grzegorczyk – est une hiérarchie de fonctions utilisée en théorie de la calculabilité. Toutes les fonctions de la hiérarchie de Grzegorczyk sont primitives récursives et toute fonction primitive récursive apparait dans cette hiérarchie. Cette hiérarchie classe les fonctions selon leur croissance. Intuitivement, les fonctions d'un niveau croissent moins vite que les fonctions des niveaux supérieurs.
Définition
modifierTout d'abord on introduit un ensemble infini de fonctions notées pour tout entier naturel .
On pose et . En d'autre terme, est la fonction d'addition et est une fonction unaire qui élève au carré son argument et ajoute .
Ensuite, pour tout entier , on définit
On peut alors définir la hiérarchie de Grzegorczyk. , la n-ième classe (ou niveau) de la hiérarchie de Grzegorczyk est le plus petit ensemble qui contient
- pour ,
- la fonction nulle,
- la fonction successeur (),
- les projections (),
et stable par
- composition de fonction (si , , ,... , sont des fonctions de , alors l'est aussi),
- récursion bornée, (si , et sont des fonctions de et que est telle que , et , alors est aussi une fonction de ).
Propriétés
modifierOn a
puisque .
En fait, l'inclusion est stricte (Rose 1984; Gakwaya 1997)
parce que l'hyperopération appartient à mais pas à .
- contient des fonctions comme , , ,
- contient toutes les fonctions d'addition telles que , ,
- contient les fonctions de multiplication, telles que , ,
- contient les fonctions exponentiation, comme , . Cet ensemble est égal à celui des fonctions élémentaires,
- contient la tétration.
Relation avec les fonctions primitives récursives
modifierLa définition de est la même que celle des fonctions primitives récursives, , sauf que la construction récursive est bornée ( pour une certaine fonction ) et les fonctions sont clairement comprises dans . Par conséquent, la hiérarchie de Grzegorczyk peut être vue comme une façon de limiter la puissance de la récursion primitive.
Il est clair que les fonctions de chaque niveau sont primitives récursives (i.e. ) et par conséquent
On peut aussi montrer que toute fonction primitive récursive est présente dans la hiérarchie de Grzegorczyk (Rose 1984; Gakwaya 1997) soit
et les ensembles forment une partition de l'ensemble des fonctions primitives récursives .
Extensions
modifierLa hiérarchie de Grzegorczyk peut être étendue aux ordinaux transfinis. On définit alors la hiérarchie de croissance rapide. Pour cela, la définition des doit être étendue pour les ordinaux limites, ils sont en effet déjà définis pour les ordinaux successeurs par . S'il y a une méthode standard de définir une suite fondamentale dont l'ordinal limite est alors la génération de ces fonctions peut se définir comme . Cependant, cette définition dépend de la suite fondamentale. Rose (1984) propose une méthode standard pour tout ordinal .
L'extension originale est due à Martin Löb et Stan S. Wainer (1970) et est parfois appelée hiérarchie de Löb–Wainer.
Bibliographie
modifier- Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, (ISBN 0-471-09585-0)
- Gakwaya, J.–S. (1997), A survey on the Grzegorczyk Hierarchy and its Extension through the BSS Model of Computability
- Grzegorczyk, A. (1953), Some classes of recursive functions, Rozprawy matematyczne, Vol 4, p. 1–45.
- Löb, M.H. and Wainer, S.S., "Hierarchies of Number Theoretic Functions I, II: A Correction," Arch. Math. Logik Grundlagenforschung 14, 1970 p. 198–199.
- Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. (ISBN 0-19-853189-3)
- Wagner, K. and Wechsung, G. (1986), Computational Complexity, Mathematics and its Applications v. 21. (ISBN 978-90-277-2146-4)