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)
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).
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
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 :
par exemple
et ainsi de suite, (n est le nombre d'éléments m écrits).
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 :
La fonction d'Ackermann s'écrit alors
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 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)
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.
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
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.
© (Copyright) Jean-Paul Davalan 2002-2014Important : 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.