# \[Théorie\] Fonction d'Ackermann **URL:** \ **Category:** Programmation\ **Created:** [Février 20, 2016, 3:54 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816 "2016-02-20T15:54:49Z")\ **Posts on this page:** 10\ **Page:** 1
**Author:** ![bert](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/b/9e8a1a/32.png) [@bert](https://www.debian-fr.org/u/bert)\ **Post date:** [Février 20, 2016, 3:54 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816/1 "2016-02-20T15:54:49Z")
Bonsoir à tous, J’aurais besoin de vos lumières au sujet de la fonction d’Ackermann (définition : [fr.wikipedia.org/wiki/Fonction\_d%27Ackermann](http://fr.wikipedia.org/wiki/Fonction_d%27Ackermann)). En admettant qu’elle croît plus vite que toutes les fonctions récursives primitives, comment démontrer qu’elle n’est pas récursive primitive ? Merci. ---
**Author:** ![Yoko](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/y/58956e/32.png) [@Yoko](https://www.debian-fr.org/u/Yoko)\ **Post date:** [Février 20, 2016, 3:54 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816/2 "2016-02-20T15:54:51Z")
D’autre te le diront mieux que moi mais en fait je pense que les fonctions récursives primitives peuvent être étudier de manière général. Ainsi on peut, peut être en déduire la croissance maximum possible. ---
**Author:** ![mattotop](https://www.debian-fr.org/user_avatar/www.debian-fr.org/mattotop/32/3942_2.png) [@mattotop](https://www.debian-fr.org/u/mattotop)\ **Post date:** [Février 20, 2016, 3:54 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816/3 "2016-02-20T15:54:52Z")
> [@bert](#): > > En admettant qu’elle croît plus vite que toutes les fonctions récursives primitives, comment démontrer qu’elle n’est pas récursive primitive ? Bah je ne connais pas le sujet, mais la réponse est dans la question: si elle croît plus vite que toutes les frp, elle croît plus vite que chacune des frp. Ce n’est donc aucune des frp. Elle est « en dehors » de l’ensemble des frp. Enfin bon, bref, elle n’est pas récursive primitive, quoi que ça veuille dire. ---
**Author:** ![Yoko](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/y/58956e/32.png) [@Yoko](https://www.debian-fr.org/u/Yoko)\ **Post date:** [Février 20, 2016, 3:54 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816/4 "2016-02-20T15:54:53Z")
J’aime pas la fonction dite itérative sur wikipedia parce qu’elle est récursive vai chercher une solution demain. ---
**Author:** ![mattotop](https://www.debian-fr.org/user_avatar/www.debian-fr.org/mattotop/32/3942_2.png) [@mattotop](https://www.debian-fr.org/u/mattotop)\ **Post date:** [Février 20, 2016, 3:54 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816/5 "2016-02-20T15:54:53Z")
d’ailleurs, c’est dit ici: [fr.wikipedia.org/wiki/Fonction\_d … \_primitive](http://fr.wikipedia.org/wiki/Fonction_d'Ackermann#Fonction_r.C3.A9cursive.2C_mais_pas_r.C3.A9cursive_primitive) > [@](#): > > La fonction d’Ackermann croît extrêmement rapidement; A(4,2) a déjà 19829 chiffres, soit bien plus que le nombre d’atomes dans l’univers actuel. 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 n’est pas primitive récursive. ---
**Author:** ![fran.b](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/f/d78d45/32.png) [@fran.b](https://www.debian-fr.org/u/fran.b)\ **Post date:** [Février 20, 2016, 3:54 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816/6 "2016-02-20T15:54:55Z")
Tu as l’ébauche de la démonstration ici [http://www2.univ-reunion.fr/~fred/Enseignement/FondementsInfo/Ackermann.html](http://www2.univ-reunion.fr/~fred/Enseignement/FondementsInfo/Ackermann.html) Comme algorithme donc la complexité met en jeu l’inverse de cette fonction, tu as la réunion (par exemple le test pour savoir si un graphe est connexe, le coup est en O(n.ß(n)) où ß est l’inverse de cette fonction). Mais la démonstration prend une centaine de pages… ---
**Author:** ![Yoko](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/y/58956e/32.png) [@Yoko](https://www.debian-fr.org/u/Yoko)\ **Post date:** [Février 20, 2016, 3:55 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816/7 "2016-02-20T15:55:00Z")
Si c’est pour la programmer (vu qu’on est dans programation je me suis amusé à en faire une fonction récursive en python : ```auto #!/usr/bin/python import sys def ack (m, n) : if m == 0 : return n + 1 if m > 0 and n == 0 : return ack(m - 1, 1) if m > 0 and n > 0 : return ack (m - 1, ack(m, n - 1)) print ack (int(sys.argv[1]), int(sys.argv[2])) ``` C’est rigolo, python ne voulant pas faire plus de 1 000 appelle récurssifs, ça plante au si on augmente un peu trop la valeurs. 😆 ---
**Author:** ![CaroleFeroce](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/c/898d66/32.png) [@CaroleFeroce](https://www.debian-fr.org/u/CaroleFeroce)\ **Post date:** [Octobre 1, 2021, 5:42 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816/8 "2021-10-01T17:42:08Z")
Hello, Avec une poignée de secondes de retard. Pour démontrer que la fonction d’Ackermann, on faisait cela en 1ère année de prépa à mon époque, il suffit de montrer qu’elle croit plus vite que toute fonction primitive récursive. C’est assez simple. ---
**Author:** ![CaroleFeroce](https://www.debian-fr.org/letter_avatar_proxy/v4/letter/c/898d66/32.png) [@CaroleFeroce](https://www.debian-fr.org/u/CaroleFeroce)\ **Post date:** [Octobre 1, 2021, 5:46 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816/9 "2021-10-01T17:46:48Z")
Connaissez vous une fonction non primitive récursive qui croit (prend des valeurs plus grandes) que la fonction d’Ackermann, mais qui, bien sûr, n’est pas Ackermann inspired (En prévention des malins qui remplaceraient ‹ +1 › par ‹ +2 › . Merci, pour info, cette fonction servira sur un prototype proto-quantic computer. ---
**Author:** ![nicola](https://www.debian-fr.org/user_avatar/www.debian-fr.org/nicola/32/8969_2.png) [@nicola](https://www.debian-fr.org/u/nicola)\ **Post date:** [Octobre 1, 2021, 5:52 UTC](https://www.debian-fr.org/t/theorie-fonction-dackermann/7816/10 "2021-10-01T17:52:02Z")
Tu peux demander sur un forum de matheux, comme [celui-là](http://www.les-mathematiques.net/phorum/index.php).