Fonction d'Ackerman

Définition sur N² de la fonction d'Ackerman

la fonction A : (m, n) |--> A(m, n) d'Ackerman 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'Ackerman 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)

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

La version rapide est équivalente à la version Lisp de Robert Kosara.
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).

Notation ‐> de John H. Conway

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

La fonction d'Ackerman 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 


0 1  2  3  4  5  6  7  8  9  10  11  12  13


1 2  3  4  5  6  7  8  9  10  11  12  13  14


2 3  5  7  9  11  13  15  17  19  21  23  25  27 


3 5  13  29  61  125  253  509  1021  2045  4093  8189  16381
32765


4 13
65533
A(4,2)                               


5 65533

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'Ackerman.

     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)=2ⁿ, B(2, n)=2^2ⁿ ...

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 Ackerman.

Récursivité

La fonction d'Ackerman 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'Ackerman (l'une ou l'autre des variantes ci-dessus) n'est pas dans cet ensemble.

Liens

Pour un premier contact, [utilisez ce formulaire] ou recopiez l'adresse qui y figure. Merci d'indiquer la page précise "http://jeux-et-mathématiques.davalan.org/" de la page du site, cela m'aidera et évitera toute confusion. Ne joignez aucun document.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès maintenant et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige 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.

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