voilà je voulais savoir à quoi correspondait la fonction f : (z,x) <math>\(\longmapsto z\uparrow^{0} x\)</math>
J'ai crus comprendre que cela correspondait à z*x, mais je ne l'ai vus nul part clairement expliqué.
Si j'ai raison, pourquoi la fonction d'Ackerman associe t-elle au couple (0, n ) , la valeur (n+1)
est-ce que cela veut dire qu'on a la relation
<math>\(z\uparrow^{n} x = z*(A(n,x) -1)\)</math>
je ne comprend pas l’intérêt du moins 1. Si cette deuxième formule est vrai
pourquoi à t'on choisi comme convention A(0, n) = (n+1) et pas A(0,n) = n ce qui aurait simplifié le formule ci dessus (qui est d'après la façon dont on m'a introduis la fonction d'Ackerman sa première raison d'être).

Bonjour,

On trouve des informations sur la fonction que tu indiques sous le nom de puissances itérées de Knuth, définies comme suit:
<math>\(\[f(z,x)=z \dagger ^n x \; , \lbrace z , x\rbrace \in N \times N ,n\geq 1\]\)</math>
avec:
<math>\(\[ x=0 \longrightarrow f(z,x)=1 \]\)</math>
<math>\(\[ n=1 \longrightarrow f(z,x)=z^x \]\)</math>

sinon la récurrence: <math>\(\[ z \dagger ^n x = z \dagger ^{n-1} (z \dagger ^{n}(x-1 ) ) \]\)</math>
A priori le cas <math>\(n=0\)</math> correpondrait simplement à z.


La relation entre cette fonction et la fonction d'Ackermannn serait plutôt donnée par :
<math>\(\[ A(n,x)=2\dagger ^{n-2} (x+3) -3\]\)</math> pour <math>\(\[ n\geq 3 \]\)</math>
avec les valeurs initiales <math>\(2+x\)</math> et <math>\(2x+3\)</math> pour 1 et 2.

Tout d'abord merci de l'aide.

Citation : nabucos

sinon la récurrence: <math>\(\[ z \dagger ^n x = z \dagger ^{n-1} (z \dagger ^{n}(x-1 ) ) \]\)</math>
A priori le cas <math>\(n=0\)</math> correpondrait simplement à z.
La relation entre cette fonction et la fonction d'Ackermannn serait plutôt donnée par :
<math>\(\[ A(n,x)=2\dagger ^{n-2} (x+3) -3\]\)</math> pour <math>\(\[ n\geq 3 \]\)</math>
avec les valeurs initiales <math>\(2+x\)</math> et <math>\(2x+3\)</math> pour 1 et 2.

Mais est-ce que tu pourrais me détailler comment tu as cette relation, ou où je peux en trouver le détail ?
Car ce n'est pas du tout comme ça que je l'ai vus.

bonsoir,

déjà comme indiqué, si tu cherches puissances itérées de Knuth tu va trouiver diverses choses.

La définition de base , on la trouve dans Wikipedia
http://fr.wikipedia.org/wiki/Notation_ [...] 3.A9r.C3.A9es
(définition point 2 du sommaire de la page)

Pour la relation avec Ackermann, par exemple
http://mabboux.pagesperso-orange.fr/Ma [...] curcive.htm#3

J'ai retrouvé la même chose à plusieurs endroits.

Donc, si tu veux aller plus loin, en cherchant, il y a matière
Personnellement, j'ai cherché un peu par curiosité car je ne suis pas du tout spécialiste, à peine plus que noms et définitions
Knuth en particulier ...ce qui m' a permis de retrouver ta fonction.
Donc je ne suis pas capable de juger de la validité de ce que tu indiques de ton coté mais un calcul ( pour les trés petits chiffres!) montre que la relation que j'indique semble fonctionner....

Bonne question pour le n+1. La raison d'être de la fonction d'Ackermann est d'exhiber une fonction récursive mais non primitive récursive (ie une fonction que l'on ne peut pas coder sans boucle while). Je suppose que le n+1 à la place du n doit être là pour simplifier la preuve de ce fait.

Personnellement, ma meilleure preuve prend comme définition A(0,x) = 2^x et A(y,0) = 1. Meilleure dans le sens où prouver la non primitive récursivité est plus simple qu'avec d'autres définitions.

nabucos --> La page de wikipédia m'a clarifié l'esprit (je ne l'aurais pas trouvé sans tes indications) , je regarderais en détail l'autre plus tard, en tout cas j'ai renoncé à lier de façon simple la fonction d'Ackerman et les puissances itérés de Knuth. (Lorsque je serais un peu plus à l'aise sur le sujet je reviendrais à la formule que tu m'as indiqué et qui pour le moment relève pour moi de la magie.

Aladis --> Ce qui est rigolo avec des notions aussi fondamentales que récursives primitives c'est que j'ai l'impression de toujours voir une nouvelle façon de les aborder : je n'avais jamais lié les histoire de boucles while et récursives primitive, pour moi c'était juste une histoire de fonction qu'on pouvait exprimer uniquement à partir de trois fonctions de bases :
le projeté , l'incrémentation, et la fonction nulle.

En tout cas merci beaucoup pour l'aide.

Pour préciser un peu mon propos vu que tu n'avais pas le lien. Comme tu le sais il y a un problème majeur en informatique : la terminaison d'un programme (qui est d'ailleurs un problème indécidable !).

Pour cela on créer une classe de programme qui s'arrête trivialement : les programmes qui n'utilisent que des boucles for. Tout est borné et tout s'arrête. On appelle cette classe "fonctions primitives récursives" dont tu connais les axiomes.

Cependant une question réside : dans les axiomes des fonctions primitives récursives, il y a la minimisation BORNÉE. Mais on peut parfaitement coder des fonctions avec un axiome de minimisation non borné. Ce sont justement les fonctions primitives non récursives.

On voit bien que la minimisation bornée est exactement une boucle for : on parcours un ensemble d'indice bien délimité et on fini forcément par en sortir. Si par contre nous n'avons pas de borne, alors c'est exactement une boucle while : on en sort si et seulement on vérifie la bonne propriété. Mais rien n'indique a priori que cette propriété sera un jour vérifiée et l'on peut boucler indéfiniment. La terminaison est donc à vérifier et cela peut être diablement complexe (imagine une fonction qui teste une à une tous les quadruplets du théorème de Fermat).

La fonction d'Ackermann montre alors que ces deux classes de fonction sont différentes, vu qu'on arrive à exhiber une fonction très concrète non primitive ércursive.