« Fonction d'Ackermann » : différence entre les versions

Dans la [[Calculabilité|théorie de la récursivité]], la '''fonction d'Ackermann''' (aussi appelée '''fonction d'Ackermann-Péter''') est un exemple simple de [[fonction récursive]] non [[Fonction récursive primitive|récursive primitive]], trouvée en [[1926 en science|1926]] par [[Wilhelm Ackermann]]. Elle est souvent présentée sous la forme qu'en a proposéproposée la mathématicienne [[Rózsa Péter]], comme une fonction à deux [[paramètre]]s [[nombreentiers entier|entiersnaturels]] naturels comme arguments et qui retourne un entier naturel comme valeur, noté en général ''A''(''nm'', ''mn'').

Dans les années 1920, [[Wilhelm Ackermann]] et [[{{Lien|Gabriel Sudan]]}}, alors étudiants sous la direction de [[David Hilbert]], étudiaient les fondements de la calculabilité. Sudan est le premier à donner un exemple de fonction récursive mais non récursive primitive, appelée alors [[fonction de Sudan]]. Peu après et indépendamment, en [[1928 en science|1928]], Ackermann a publié son propre exemple de fonction récursive mais non récursive primitive<ref>{{en}}Cristian Calude, [[Solomon Marcus]] et Ionel Tevy, « The first example of a recursive function which is not primitive recursive », ''[[Historia Mathematica|Historia Math.]]'', {{vol.|6}}, {{numéro|4}}, [[1979 en science|1979]], pp{{p.|380-384}}. 380–84</ref>. À l'origine, Ackermann considéra une fonction A ''ϕ''(''m'', ''n'', ''p'') dépendant de trois variables, et consistant, si ''p'' > 0, à calculer la puissance itérée ''p'' – 1 fois de ''m'' par ''n'', c'est-à-dire {{nobr|''m'' → ''n'' → (''p'' pour– utiliser1)}} laen [[Notation des flèches chaînées de Conway|notation de Conway]].

Ackermann démontra que sa fonction ''Aϕ'' était bien une fonction récursive, i.e.c'est-à-dire une fonction qu'un [[ordinateur]] idéalisé peut calculer. Dans ''Sur l'infini''<ref>{{Article|lang=de|first=David|nom=Hilbert|titre=Über das Unendliche|lien périodique=Mathematische Annalen|revue=Mathematische Annalen|vol=95|year=1926|p.=161-190|url=http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0095&DMDID=DMDLOG_0015}}, trad. : {{en}} ''[http://www.math.dartmouth.edu/~matc/Readers/HowManyAngels/Philosophy/Philosophy.html On the infinite]'' et {{Article|lien auteur=André Weil|first=André|nom=Weil|lien périodique=Acta Mathematica|revue=Acta Mathematica|year=1926|vol=48|issue=1-2|p.=91-122|titre=Sur l'infini|doi=10.1007/BF02629757}}.</ref>, David Hilbert conjectura que la fonction d'Ackermann n'était pas [[Fonction récursive primitive|primitivement récursive]]. Cette conjecture fut établie par Ackermann lui-même dans son article ''Zum Hilbertschen Aufbau der reellen Zahlen''<ref>{{Article|lang=de|first=Wilhelm |nom=Ackermann, [|url=http://gdz.sub.uni-goettingen.de/en/dms/loader/img/?PPN=PPN235181684_0099&DMDID=DMDLOG_0009 « |titre=Zum Hilbertschen Aufbau der reellen Zahlen », ''[[Mathematische Annalen|''revue=Mathematische Annalen'']], {{|vol.=99|99}}, [[year=1928 en science|1928]], ppp. 118–33]=118-133}}.</ref>. ''Sur l'infini'' était l'article le plus important de Hilbert sur les bases[[fondements des mathématiques]], servant de cœur à [[Programme de Hilbert|son programme]] pour fixer la base des [[nombres transfinis]].

Une fonction semblable de seulement deux variables — correspondant à ''ϕ''(2, ∙, ∙) — fut donnée plus tard par [[Rózsa Péter]] et [[{{Lien|Raphael Robinson]]}} ; c'est cette dernière qui est connue aujourd'hui sous le nom de fonction d'Ackermann.

La fonction d'Ackermann, montre que la notion de calculabilité introduite par les fonctions récursives primitives ne correspond pas à la notion de calculabilité la plus générale, celle mentionnée par la [[thèse de Church]]. En effet, la fonction d'Ackermann est calculable au sens de Turing et de Church, mais pas par une fonction récursive primitive. Cet exemple montre que la thèse de Church ne concerne pas ''tous'' les systèmes de calcul. Les fonctions récursives primitives permettent bien de définir la plupart des fonctions usuelles, mais non équivalents aux machines de Turing et au lambda-calcul. La calculabilité de la fonction d'Ackermann sert ici de critère distinctif, ce qui fait son importance épistémologique.

:''A''(1, ''n'') = 2 + (''n'' + 3) -– 3

:''A''(2, ''n'') = 2 × (''n'' + 3) -– 3

:''A''(3, ''n'') = 2 ^ (''n'' + 3) -– 3

:''A''(4, ''n'') = 2 ↑↑ (''n'' + 3) -– 3

:''A''(5, ''n'') = 2 ↑↑ (2 ↑↑ (2 ↑↑ (... ↑↑2))) -– 3 &nbsp;&nbsp;&nbsp; (''n'' + 3 deux)

:&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = 2↑↑↑(''n'' + 3) -– 3

:''A''(6, ''n'') = 2↑↑↑↑(''n'' + 3) -– 3 {{etc.}}

On montre assez facilement par récurrence que :

:''A''(''u'', ''v'') = 2↑^{(''u''-2–2)}(''v'' + 3) -– 3 = ''ϕ''(2, ''v'' + 3, ''u'' – 1) – 3.

La fonction d'Ackermann demandant beaucoup de calculs même pour de petites entrées, elle est parfois utilisée comme programme de test d'une implémentation d'un langage de programmation : en particulier, elle utilise de façon très exigeante la [[récursivité]], de même que ses consœurs ''fib'' ([[suite de Fibonacci]]) et ''tak'' ([[fonction de Takeuchi]]).

En plus de tester directement les performances d'un langage de programmation, la fonction d'Ackermann a été utilisée comme exemple pour étudier des transformations de programme et des optimisations, en particulier dans le domaine de la spécialisation de programmes et de l'{{Lien|fr=évaluation partielle|lang=en|trad=Partial Evaluation}}<ref>{{en}} Yanhong A. Liu et Scott D. Stoller, « [http://www.cs.stonybrook.edu/~liu/papers/Ackermann-PEPM03.pdf Optimizing Ackermann's Function by Incrementalization] », ''Workshop on Partial Evaluation and Semantics Based Program Manipulation'', [[2003 en science|2003]].</ref>.