Voir la source de Fonction d'Ackermann

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ée la mathématicienne [[Rózsa Péter]], comme une fonction à deux paramètres [[entiers naturels]] comme arguments et qui retourne un entier naturel comme valeur, noté en général ''A''(''m'', ''n'').

== Histoire ==

Dans les années 1920, [[Wilhelm Ackermann]] et [[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]], {{p.|380-384}}.</ref>. À l'origine, Ackermann considéra une fonction ''ϕ''(''m'', ''n'', ''p'') dépendant de trois variables. 

Ackermann démontra que sa fonction ''ϕ'' était bien une fonction récursive, 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| récursive primitive]]. 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|revue=Mathematische Annalen|vol=99|year=1928|p.=118-133}}.</ref>. ''Sur l'infini'' était l'article le plus important de Hilbert sur les [[fondements des mathématiques]], servant de cœur à [[Programme de Hilbert|son programme]] pour fixer la base des [[nombres transfinis]].

Une fonction de seulement deux variables  fut donnée plus tard par [[Rózsa Péter]] et [[Raphael Robinson]] ; c'est cette dernière qui est connue aujourd'hui sous le nom de fonction d'Ackermann.

== Définition ==

La fonction d'Ackermann-Péter est définie [[récursivité|récursivement]] comme suit :

: <math> A(m, n) = 
  \begin{cases}
     n+1 & \mbox{si } m = 0 \\
     A(m-1, 1) & \mbox{si } m > 0 \mbox{ et } n = 0 \\
     A(m-1, A(m, n-1)) & \mbox{si } m > 0 \mbox{ et } n > 0.
  \end{cases}
</math>

Autrement dit :

:<math>A(0, n) = n+1\,</math>
:<math>A(m+1, 0) = A(m, 1)\,</math>
:<math>A(m+1, n+1) = A(m, A(m+1, n))\,</math>

On montre alors que :
:<math>A(1, n) = 2 + (n + 3) - 3</math>
:<math>A(2, n) = 2 \times (n + 3) - 3</math>
:<math>A(3, n) = 2^{n + 3} - 3</math>
:<math>A(4, n) = 2^{2^{2^{\cdots^2}}} - 3</math> avec (''n'' + 3) deux empilés, noté également <math>2\uparrow\uparrow(n + 3) - 3</math> en utilisant la [[notation des puissances itérées de Knuth]]. 
:<math>A(5,n) = 2 \uparrow\uparrow (2 \uparrow\uparrow (2 \uparrow\uparrow (\cdots \uparrow\uparrow 2))) - 3</math> avec (''n'' + 3) deux, également noté <math>2\uparrow\uparrow\uparrow(n+3)-3</math>.
et plus généralement :
: <math> A(m, n) = 2 \uparrow^{(m-2)}(n+3)-3</math>

Ackermann a initialement proposé cette fonction  à trois paramètres<ref name=Ackermann120>{{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|revue=Mathematische Annalen|vol=99|year=1928|p.=118-133}}, p. 120</ref> :

:<math> \begin{cases}
\phi(m, n, 0) = m + n \\
\phi(m, 0, p+1) = \alpha(m,p) = \begin{cases} 0, & \text{si }p=0 \\ 1, & \text{si }p=1\\ m, & \text{si }p \ge 2\end{cases} \\
\phi(m, n+1, p+1) = \phi(m, \phi(m, n, p+1), p)
\end{cases}\,\!</math>

Elle satisfait aux égalités suivantes :

:<math>\phi(a, b, 0) = a+b\,</math>
:<math>\phi(a, b, 1) = a \cdot b</math>
:<math>\phi(a, b, 2) = a^b\,</math>
et, plus généralement<ref name=Ackermann120/>, si <math> f_n</math> est définie par 
:<math> f_n(c)=\phi(a,c,n)</math>
<math>\phi(a,b,n+1)</math> est la {{math|''b''{{exp|ième}}}} [[Fonction itérée|itérée]] de <math> f_n</math> en <math>\alpha(a,n)</math>

== Table de valeurs ==

{| class="wikitable"
|+ Valeurs de ''A''(''m'',&nbsp;''n'')
|-----
! ''m''\''n''
! 0
! 1
! 2
! 3
! 4
! ''n''
|-----
! 0
| 1 || 2 || 3 || 4 || 5 || ''n''&nbsp;+&nbsp;1
|-----
! 1
| 2 || 3 || 4 || 5 || 6 || ''n''&nbsp;+&nbsp;2
|-----
! 2
| 3 || 5 || 7 || 9 || 11 || 2''n''&nbsp;+&nbsp;3
|-----
! 3
| 5 || 13 || 29 || 61 || 125 || 2<sup>''n''&nbsp;+&nbsp;3</sup>&nbsp;−&nbsp;3
|-----
! 4
| 13 || 65533 || 2<sup>65536</sup>&nbsp;−&nbsp;3
| ''A''(3,&nbsp;2<sup>65536</sup>&nbsp;−&nbsp;3)
| ''A''(3,&nbsp;''A''(4,&nbsp;3))
| 2<sup>2<sup>...<sup>2</sup></sup></sup>&nbsp;−&nbsp;3 (''n''&nbsp;+&nbsp;3 termes)
|-----
! 5
| 65533 || ''A''(4,&nbsp;65533) || ''A''(4,&nbsp;''A''(5,&nbsp;1))
| ''A''(4,&nbsp;''A''(5,&nbsp;2)) || ''A''(4,&nbsp;''A''(5,&nbsp;3))
|-----
! 6
| ''A''(5,&nbsp;1) || ''A''(5,&nbsp;''A''(5,&nbsp;1))
| ''A''(5,&nbsp;A(6,&nbsp;1))
| ''A''(5,&nbsp;''A''(6,&nbsp;2)) || ''A''(5,&nbsp;''A''(6,&nbsp;3))
|}

== Importance épistémologique ==

La seule opération effectuée lors du déroulement de la fonction d'Ackermann est l'ajout de 1 (lorsque m est nul). Malgré cela, cette fonction croît extrêmement rapidement : ''A''(4,2) a déjà 19729 chiffres, et représente ''bien plus'' que le nombre d'atomes estimé dans l'univers. Cette extrême croissance peut être exploitée pour montrer que la fonction ''f'' définie par ''f''(''n'') = ''A''(''n'', ''n'') croît plus rapidement que n'importe quelle [[fonction récursive primitive]] et ainsi que ''A'' n'en est pas une.

Cette fonction est néanmoins définissable par récursion primitive d'ordre supérieur ([[système T]] de [[Gödel]] et ses extensions).  Elle est aussi calculable par une [[machine de Turing]]. La fonction d'Ackermann constitue donc un exemple de fonction récursive, mais non récursive primitive. C'est peut-être l'exemple le plus cité d'une telle fonction (en particulier chez [[Knuth]]). 

La fonction d'Ackermann montre que la notion de calculabilité introduite par les seules fonctions récursives primitives ne correspond pas à la notion de calculabilité la plus générale, celle de  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.

D'un point de vue historique, il est intéressant de noter que les premiers programmeurs qui utilisaient [[Fortran]] affirmaient sans preuve qu'il avait la complexité des fonctions récursives.  Pour y apporter une preuve, le logicien [[Henry Gordon Rice|Rice]] a proposé en 1965 un programme en [[Fortran]] (bien sûr non récursif) qui calculait la fonction d'Ackermann<ref> H. G. Rice, ''Recursion and Iteration'', Com. A.C.M., vol. 8, 1965, p. 114-115.</ref>.

== Réciproque ==

L'inverse de la fonction d'Ackermann est aussi utilisée. Puisque la fonction ''f'' définie par ''f''(''n'') = ''A''(''n'',''n'') considérée précédemment croît réellement très vite, sa réciproque croît vraiment très lentement.
Elle apparaît notamment en [[algorithmique]], pour exprimer des [[complexité en temps|complexités]]. Dans ce domaine elle est souvent notée <math>\alpha</math><ref name=invack>{{lien web|url=http://www.gabrielnivasch.org/fun/inverse-ackermann|titre=Inverse Ackermann without pain|auteur=Gabriel Nivasch|date=2009}}.</ref>. On la trouve par exemple dans l'analyse de certaines structures de données comme l'[[Union-Find]], dans un algorithme de calcul de l'[[arbre couvrant de poids minimal]] et en [[géométrie algorithmique]]<ref name=invack/>. Elle peut être définie simplement sans faire appel à la fonction d'Ackermann, en définissant la hiérarchie inverse d'Ackermann (qui fait aussi apparaître le [[logarithme itéré]])<ref name=invack/>{{,}}<ref>{{lien web|url=http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf|titre=Understanding the inverse Ackermann function|auteur=Raimund Seidel|site=22nd European Workshop on Computational Geometry|date=2006}}.</ref>.

== Applications pratiques ==

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|trad=Partial Evaluation|lang=en|fr=évaluation partielle}}<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>.

== Références ==
{{références}}

== Voir aussi ==
=== Articles connexes ===
* [[Explosion combinatoire]]
* [[Hyperopération]]
* [[Hiérarchie de croissance rapide]]

=== Liens externes ===
* [http://rosettacode.org/wiki/Ackermann_function Implémentation dans divers langages de programmation] sur rosettacode.org
* ''[http://blog.smwhr.net/2007/09/30/la-course-aux-grands-nombres/ La course aux grands nombres]'' de [[Scott Aaronson]], traduit sur le blog smwhr, et sa version originale : ''[http://www.scottaaronson.com/writings/bignumbers.html Who can name the biggest number?]'' (1999), un essai sur la notion de grand nombre.

{{Portail|logique|informatique théorique}}

[[Catégorie:Calculabilité]]
[[Catégorie:Fonction remarquable|Ackermann]]
[[Catégorie:Grand nombre]]