Accueil / Mots / Suites / fonction d'Ackermann

Fonction d'Ackermann

Définition sur N2 de la fonction d'Ackermann

la fonction A : (m, n) |--> A(m, n) d'Ackermann est définie sur N × N par :

          Si m = 0, alors A(0, n) = n+1,
          sinon si n=0, A(m, 0) = A(m-1, 1)
          sinon A(m, n) = A(m-1, A(m, n-1))


La fonction d'Ackermann croît très rapidement, en particulier n |--> A(n, n) croît plus rapidement que n'importe quelle fonction polynôme ou même exponentielle.


Calcul de A(m, n)

fonction d'Ackermann


cherche exemple efface

En Scheme

Le programme suivant est écrit en 'Scheme' et peut être exécuté avec Mit-scheme
        (define (A m n)
          (cond ((= m 0) (+ n 1))
                ((= n 0 ) (A (- m 1) 1))
                (else (A (- m 1) (A m (- n 1))))))
Pour lancer le programme :
        scheme -load ack.s
Exemple de calcul :
        1 ]=> (A 3 8)

        ;Value: 2045
Les formules données au paragraphe suivant pour m inférieur ou égal à 4, permettent un gain de temps appréciable lors de certains calculs.
La première se trouve dans la définition, les autres se démontrent très facilement par récurrence, (voir la démo pour les premières valeurs de m).

Notations

^ de Donald Knuth

Les notations ^^ utilisées dans les expressions ci-dessous sont de Donald Knuth.

    A(0, n) = n+1,  A(1, n) = n+2,  A(2, n) = 2*n + 3,  A(3, n) = 2^(n+3)-3,
    A(4, n) = 2^2^2^... 2^2^16 -3 = 2^^(n + 3) - 3, A(5, n) = 2^^^(n + 3) - 3
    A(6, n) = 2^^^^(n + 3) - 3 ...

Leur définition est une sorte de généralisation des puissances :
m^n = m.m.m...m (n facteurs) est la notation exponentielle habituelle des puissances,
m^^n = m^m^m^m...^m=m^(m^(m^(m...^m)...)) est une exponentielle itérée,
par exemple A(4, 1)=2^^(1+3) -3 = 2^^4 -3 = 2^2^2^2 -3 = 65536 -3 = 65533
m^^^n=m^^m^^m^^m...^^m
m^^^^n=m^^^m^^^m^^^m...^^^m
et ainsi de suite, (n est le nombre d'éléments m écrits).


Nombre d'Ackermann

Notation ‐> de John H. Conway

La notation de Conway est : a --> b --> c = a^^...^^b (avec c flèches ^)

La fonction d'Ackermann s'écrit alors A(m,n)= 2 -> (n+3) -> (m-2) -3


Simples calculs


A(m,n)0 1 2 3 4 5 6 7 8 9 10 11 12
01 2 3 4 5 6 7 8 9 10 11 12 13
12 3 4 5 6 7 8 9 10 11 12 13 14
23 5 7 9 11 13 15 17 19 21 23 25 27
35 13 29 61 125 253 509 1021 2045 4093 8189 16381 32765
413 65533 A(4,2)                    
565533                       

Le calcul de A(4, 2) est le suivant :
    A(4, 2) = A(3, A(4, 1)) = A(3, 2^16 -3)) = 2^2^16 -3 = 20035...6733
Le résultat s'obtient facilement grâce au logiciel de calcul multiprécision bc. On peut aussi déterminer le nombre de chiffres du résultat : 19729 en base dix.
La valeur semble bien celle trouvée différemment par (1)
    echo 'a=2^(2^16)-3;length(a)'|bc -q
Le calcul de A(4,3) = A(3, A(4,2))=A(3, 2^(2^16) -3)=2^(2^(2^16))-3 dépasse les possibilités de bc.

Autres définitions

Le livre « Structure et interprétation des programmes informatiques » de Harold Abelson/ Gerald Jay Sussman avec Julie Sussman, à InterEditions donne une version différente de la fonction d'Ackermann.
     Si n = 0, alors B(m, 0) = 0
     sinon si m = 0, alors B(0, n) = 2n
     sinon si n = 1, alors B(m, 1) = 2
     sinon A(m, n) = B(m-1, B(m, n-1))
On peut voir que pour cette autre fonction notée B et pour n>0 on a B(0, n)=2n, B(1, n)=2n, B(2, n)=22n ...
Dans le livre de logique mathématique de R. Cori et D. Lascar on a la définition :
      i)  pour tout entier x, E(0, x)=2^x;
      ii) pour tout entier y, E(y, 0)=1,
      iii) pour tous entiers x et y, E(y+1, x+1)=E(y,E(y+1,x)).
toutes les versions données dans cette page sont des simplifications de la fonction construite à l'origine par Ackermann.

Récursivité

La fonction d'Ackermann n'est pas récursive primitive.

Voir le tome II du livre de R. Cori et D. Lascar pour les définitions et pour une démonstration.
L'ensemble des fonctions récursives primitives est l'ensemble qui contient les fonctions constantes, les fonctions projections et la fonction successeur et qui est clos pour les définitions par récurrence et pour la composition.
La fonction d'Ackermann (l'une ou l'autre des variantes ci-dessus) n'est pas dans cet ensemble.


Liens


Accueil / Mots / Suites / fonction d'Ackermann

















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014