$\"Accueil\"$

Accueil
Plan du site
Bloc notes

Jeux

Graphes
Combinatoire
Arithmétique
Algèbre
Analyse

Probabilités
Géométrie
Automates
Informatique
Divers
Lycée

Liens

Forum (modéré)

NJAS
On-Line Encyclopedia
of Integer Sequences

UniversitySurf.net
Votre portail e-Learning

L'INVERSEUR
de Plouffe

CultureMATH
ENSup. et Minist. EN

MaMuX
IRCAM Mathématiques, musique et relations avec d'autres disciplines

Votez dès le 15/10/2008

Plus de 200 000 signatures pour l'abandon d'Edvige recueillies depuis le 10 juillet 2008

La version 2.0 n'est pas plus acceptable que la version 1.0.
À Paris comme dans toutes les régions de France, citoyens et élus diront « Non à EDVIGE » au cours de rassemblements organisés par le Collectif national et par un nombre croissant de Collectifs locaux.

Accueil / Mots / Suites / fonction d'Ackerman

Fonction d'Ackerman

(Retour à l'Index général des suites)

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

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

The Ackermann Function [Robert Kosara]

Wikipedia : Gerald Jay Sussman

Mit-Scheme

InterEditions

Peter Hinely ackermann.zip Dylan Programming Language

Prime Curios 71 divides all values of Ackerman's function A(m,n) for sufficiently large m. 61 is the largest prime of the form A(m,m)

big numbers [Susan Stepney] Knuth's up-arrow notation. The up-arrow notation has a close relationship to the Ackermann function. Googol. Skewes' number.

Donald Knuth est aussi l'auteur de TeX and METAFONT, du livre 'Art of Computer Programming' ...

Large Numbers Robert Munafo

Logique mathématique René Cori, Daniel Lascar

Graham's number The last entry in The Penguin Dictionary of Curious and Interesting Numbers by David Wells.

ackermann benchmark Each program should calculate the Ackermann function using the same naïve recursive-algorithm. The Computer Language Shootout Benchmarks