[Théorie] Fonction d'Ackermann

Programmation
1

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

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.

2

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.

3

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.

4

J’aime pas la fonction dite itérative sur wikipedia parce qu’elle est récursive vai chercher une solution demain.

5

d’ailleurs, c’est dit ici:
fr.wikipedia.org/wiki/Fonction_d … _primitive

6

Tu as l’ébauche de la démonstration ici 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…

7

Si c’est pour la programmer (vu qu’on est dans programation je me suis amusé à en faire une fonction récursive en python :

#!/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. :laughing:

8

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.

9

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.

10

Tu peux demander sur un forum de matheux, comme celui-là.