En théorie de la calculabilité , la fonction d'Ackermann , nommée d'après Wilhelm Ackermann , est l'un des exemples les plus simples et les plus anciens de fonction totalement c...
Worldlex WikiContenu en francaisLecture gratuite
théorie de la calculabilité , la fonction d'Ackermann , nommée d'après Wilhelm Ackermann , est l'un des exemples les plus simples et les plus anciens de fonction totalement calculable qui n'est pas primitive récursive . Toutes les fonctions primitives récursives sont totales et calculables, mais la fonction d'Ackermann illustre le fait que toutes les fonctions totalement calculables ne sont pas primitives récursives. Elle est essentiellement construite en diagonalisant une suite de fonctions primitives récursives choisies dans la hiérarchie de Grzegorczyk . Ceci fait de la fonction d'Ackermann le premier point limite de cette hiérarchie à croissance rapide .
Après la publication par Ackermann de sa fonction (qui comportait trois arguments entiers non négatifs), de nombreux auteurs l'ont modifiée pour répondre à divers besoins, si bien qu'aujourd'hui, l'expression « fonction d'Ackermann » peut désigner l'une des nombreuses variantes de la fonction originale. Une version courante est la fonction d'Ackermann-Péter à deux arguments , développée par Rózsa Péter et Raphael Robinson . Cette fonction est définie à partir de la relation de récurrence avec des cas de base appropriés . Sa valeur croît très rapidement ; par exemple, elle atteint 19 729 décimales.
et car elle étend ces opérations de base d'une manière comparable aux hyperopérations : 2" 2
3 \\end{align}" 3\end{aligned
(Outre son rôle historique de fonction totalement calculable mais non primitive récursive, la fonction originale d'Ackermann est considérée comme étendant les opérations arithmétiques de base au-delà de l'exponentiation, bien que pas aussi facilement que les variantes de la fonction d'Ackermann spécifiquement conçues à cette fin, telles que la séquence d'hyperopérations de Goodstein .)
Dans Sur l'infini , David Hilbert a émis l'hypothèse que la fonction d'Ackermann n'était pas primitive récursive, mais c'est Ackermann, le secrétaire personnel et ancien étudiant de Hilbert, qui a en fait prouvé l'hypothèse dans son article Sur la construction des nombres réels par Hilbert .
Rózsa Péter et Raphael Robinson ont par la suite développé une version à deux variables de la fonction d'Ackermann qui est devenue préférée par presque tous les auteurs.
La séquence d'hyperopération généralisée , par exemple , est également une version de la fonction d'Ackermann.
Comparée à la plupart des autres versions, la fonction de Buck ne comporte aucun décalage superflu :
De nombreuses autres versions de la fonction d'Ackermann ont été étudiées.
Définition
Définition : en tant que fonction m -aire
La fonction originale à trois arguments d'Ackermann est définie récursivement comme suit pour les entiers non négatifs et :
2 \\\\ \\varphi(m, n, p) &= \\varphi(m, \\varphi(m, n-1, p), p - 1) && \ ext{for } n, p > 0 \\end{align}" 2\\\varphi (m,n,p)&=\varphi (m,\varphi (m,n-1,p),p-1)&&{ ext{pour }}n,p>0\end{aligned
Parmi les différentes versions à deux arguments, celle développée par Péter et Robinson (appelée « la » fonction d'Ackermann par la plupart des auteurs) est définie pour les entiers non négatifs et comme suit :
Calcul par TRS, basé sur une fonction 1-aire itérée
La définition des fonctions d'Ackermann 1-aires itérées conduit à des règles de réduction différentes
Comme la composition de fonctions est associative, au lieu de la règle r6, on peut définir
Comme dans la section précédente, le calcul peut être implémenté avec une pile.
Initialement, la pile contient les trois éléments .
Ensuite, les trois éléments supérieurs sont remplacés de manière répétée selon les règles
Schématiquement, en partant de :
TANT QUE longueur de pile <> 1 { POP 3 éléments ; PUSH 1 ou 3 ou 5 éléments, en appliquant les règles r4, r5, r6 ; }
Exemple
En entrée, les configurations de pile successives sont
Les égalités correspondantes sont
Lorsque la règle de réduction r7 est utilisée au lieu de la règle r6, les remplacements dans la pile suivront
Les configurations d'empilement successives seront alors
Les égalités correspondantes sont
Remarques
Pour une entrée donnée, les TRS présentés jusqu'ici convergent en le même nombre d'étapes. Ils utilisent également les mêmes règles de réduction (dans cette comparaison, les règles r1, r2 et r3 sont considérées comme identiques aux règles r4, r5 et r6/r7 respectivement). Par exemple, la réduction converge en 14 étapes : 6 × r1, 3 × r2, 5 × r3. La réduction converge également en 14 étapes : 6 × r4, 3 × r5, 5 × r6/r7. Les TRS diffèrent par l'ordre d'application des règles de réduction.
Lorsque la valeur de est calculée selon les règles {r4, r5, r6}, la longueur maximale de la pile reste inférieure à . Lorsque la règle de réduction r7 est utilisée à la place de la règle r6, la longueur maximale de la pile atteint seulement . La longueur de la pile reflète la profondeur de récursion. Comme la réduction selon les règles {r4, r5, r7} implique une profondeur de récursion maximale plus faible, ce calcul est plus efficace à cet égard.
ou, après suppression de la constante 2 de la liste des paramètres, en termes de fonction de Buck
0 \\\\ \\end{cases}" 0\\\end{cases
La fonction de Buck , une variante de la fonction d'Ackermann, peut être calculée avec les règles de réduction suivantes :
Au lieu de la règle b6, on peut définir la règle
Pour calculer la fonction d'Ackermann, il suffit d'ajouter trois règles de réduction.
Ces règles prennent en charge le cas de base , l'alignement et le correctif (-3).
Exemple
Calculer
en utilisant la règle de réduction :
Les égalités correspondantes sont
lorsque le TRS avec la règle de réduction est appliqué :
lorsque le TRS avec la règle de réduction est appliqué :
Remarques
Le calcul de selon les règles {b1 - b5, b6, r8 - r10} est profondément récursif. La profondeur maximale des itérations est . Le problème vient de l'ordre d'exécution des itérations : . La première itération disparaît seulement après le déroulement complet de la séquence.
Le calcul selon les règles {b1 - b5, b7, r8 - r10} est plus efficace à cet égard. L'itération simule la boucle répétée sur un bloc de code. L'imbrication est limitée à un niveau de récursion par fonction itérée.
Un gain réel de temps d'exécution ne peut être obtenu qu'en évitant de recalculer systématiquement les sous-résultats. La mémoïsation est une technique d'optimisation qui consiste à mettre en cache les résultats des appels de fonction et à les restituer lorsque les mêmes entrées sont utilisées à nouveau. Voir par exemple
des nombres énormes
Pour démontrer comment le calcul des résultats se fait en de nombreuses étapes et en un grand nombre :
Tableau des valeurs
Le calcul de la fonction d'Ackermann peut être reformulé à l'aide d'un tableau infini. On place d'abord les nombres naturels sur la première ligne. Pour trouver un nombre dans le tableau, on prend celui qui se trouve immédiatement à sa gauche. On utilise ensuite ce nombre pour chercher le nombre recherché dans la colonne correspondante, une ligne plus haut. S'il n'y a pas de nombre à sa gauche, on consulte simplement la colonne « 1 » de la ligne précédente. Voici un extrait du coin supérieur gauche du tableau :
Valeurs de A ( m , n )
1
2
3
4
5
6
2
3
5
7
9
11
3
5
13
29
61
125
4
13
65533
2 65536 – 3
5
65533
6
m
Les nombres ici exprimés uniquement par exponentiation récursive ou par flèches de Knuth sont très grands et prendraient trop de place pour être notés en chiffres décimaux simples.
Malgré les grandes valeurs présentes dans cette première partie du tableau, des nombres encore plus grands ont été définis, comme le nombre de Graham , qui ne peut être représenté par un petit nombre de flèches de Knuth. Ce nombre est construit selon une technique similaire à l'application récursive de la fonction d'Ackermann à elle-même.
Il s'agit d'une répétition du tableau ci-dessus, mais avec les valeurs remplacées par l'expression correspondante de la définition de la fonction afin de mettre clairement en évidence le modèle :
Valeurs de A ( m , n )
ordre lexicographique des paires, qui est un bon ordre , tout comme l'ordre des entiers non négatifs ; cela signifie qu'on ne peut pas descendre dans cet ordre une infinité de fois de suite.) Cependant, lorsque diminue, il n'y a pas de limite supérieure à sa croissance — et celle-ci est souvent importante.
Pour de petites valeurs de m comme 1, 2 ou 3, la fonction d'Ackermann croît relativement lentement avec n (au plus exponentiellement ). Pour n = 1, en revanche, elle croît beaucoup plus rapidement ; même n = 1, elle vaut environ 2,00353 exponentielle , la factorielle, les multifactorielles et superfactorielles , et même les fonctions définies à l'aide de la notation de Knuth (sauf lorsque la flèche vers le haut indexée est utilisée). On constate que est comparable à dans la hiérarchie des fonctions à croissance rapide . Cette croissance extrême permet de démontrer que , qui est évidemment calculable sur une machine à mémoire infinie comme une machine de Turing et est donc une fonction calculable , croît plus vite que toute fonction récursive primitive et n'est donc pas une fonction récursive primitive.
Non primitif récursif
La fonction d'Ackermann croît plus rapidement que toute fonction récursive primitive et n'est donc pas elle-même une fonction récursive primitive.
Croquis de preuve :
Les fonctions récursives primitives sont construites à partir de fonctions de base par composition et récursivité primitive, et leur complexité croît selon un certain rythme. On définit, de manière constructive, une hiérarchie de fonctions totales par :
où désigne l'itération -fois de sur l'entrée . Cette hiérarchie croît strictement plus vite avec l'augmentation de , et chaque fonction récursive primitive est finalement majorée par un certain . Ceci peut être démontré par induction structurelle sur les définitions des fonctions récursives primitives.
Cependant, la fonction d'Ackermann finit par dépasser tout seuil ; pour tout , il existe tel que pour tout suffisamment grand . Ainsi, croît plus rapidement que toute fonction récursive primitive et n'est donc pas une fonction récursive primitive. \\operatorname{FGH}_k(n)" \operatorname {FGH} _{k}(n)
Inverse
fonction inverse , f⁻¹ , croît très lentement. Cette fonction d'Ackermann inverse f⁻¹ est généralement notée α . En fait, α ( n ) est inférieur à 5 pour toute taille d'entrée pratique n , puisque
Cette inversion se manifeste dans la complexité temporelle de certains algorithmes, comme la structure de données des ensembles disjoints et l'algorithme de Chazelle pour les arbres couvrants minimaux . On utilise parfois la fonction originale d'Ackermann ou d'autres variantes dans ces contextes, mais leur complexité augmente toujours de façon similaire. En particulier, certaines fonctions modifiées simplifient l'expression en éliminant le terme −3 et les termes analogues.
Une variante à deux paramètres de la fonction inverse d'Ackermann peut être définie comme suit, où est la fonction partie entière :
Cette fonction intervient dans des analyses plus précises des algorithmes mentionnés précédemment et fournit une borne temporelle plus fine. Dans la structure de données des ensembles disjoints, m représente le nombre d'opérations et n le nombre d'éléments ; dans l'algorithme de l'arbre couvrant minimal, m représente le nombre d'arêtes et n le nombre de sommets. Il existe plusieurs définitions légèrement différentes de fonction plafond .
D’autres études pourraient définir une fonction inverse de un où m est fixé à une constante, de sorte que l’inverse s’applique à une ligne particulière.
L'inverse de la fonction d'Ackermann est récursive primitive, puisqu'elle est récursive primitive de graphe, et elle est majorée par une fonction récursive primitive.
L' inverse de la fonction d'Ackermann apparaît dans certains résultats de complexité temporelle. Par exemple, la structure de données d'ensembles disjoints prend un temps amorti par opération proportionnel à l'inverse de la fonction d'Ackermann et ne peut être accélérée dans le cadre du modèle de complexité computationnelle par sonde cellulaire
En géométrie discrète
Certains problèmes de géométrie discrète liés aux suites de Davenport-Schinzel admettent des bornes de complexité dans lesquelles apparaît la fonction d'Ackermann inverse. Par exemple, pour les segments de droite du plan, la face non bornée de l' arrangement des segments a une complexité O(n) , et certains systèmes de segments de droite ont une face non bornée de complexité O(n ) .
L'article fondateur de Sundblad a été repris par Brian Wichmann (co-auteur du benchmark Whetstone ) dans une trilogie d'articles écrits entre 1975 et 1982.
Worldlex Wiki 
2 
3\end{aligned 
0 
\operatorname {FGH} _{k}(n)