La légendaire fonction d'Ackermann

[Dinozzo13]

Bonsoir, cette fois j'aurai besoin d'aide pour un exercice concernant la fonction d'Ackermann car je me perds dans mes calculs, merci d'avance pour toutes aide :++:
La fonction d’Ackermann associe à deux entiers positifs m et n un entier (m;n). Nous admettrons que les trois propriétés suivantes permettent d’obtenir l’image de n’importe quel couple d’entiers positifs.



On me demande de calculer

Si et alors
Calculons :
Si et alors
Calculons :
Si alors
Calculons :
Si et alors
Calculons :
Si alors
Calculons :
Si alors
Et donc par suite :
Si alors et donc
Mais après je suis un peu perdu, j'ai l'impression que mes calculs ne me mènent nulle part.

[bombastus]

Salut,

Elle est pas banale cette fonction!

dans tes 2 dernières lignes, tu peux calculer la valeur de f(0,2), donc tu dois pouvoir continuer avec f[1,f(0,2)]

[Skullkid]

Salut, une remarque de mise en forme : c'est assez lourd tous tes "si n = machin et m = truc alors...". Ce serait à mon avis plus clair et bien moins embrouillant d'écrire

f(2,2) = f(1+1,1+1) = f(1,f(2,1))
f(2,1) = f(1+1,0+1) = f(1,f(2,0)) = f(1,f(1,1)) etc

En plus comme ça t'as un calcul par ligne, tu peux facilement remonter, trouver les valeurs que tu as déjà calculées, toussa. Au cas où tu n'aurais pas encore fini le calcul, comme c'est facile de s'y perdre, je te le mets en entier.

f(2,2) = f(1+1,1+1) = f(1,f(2,1))
f(2,1) = f(1+1,0+1) = f(1,f(2,0)) = f(1,f(1,1))
f(1,1) = f(0+1,0+1) = f(0,f(1,0)) = f(0,f(0,1)) = f(0,2) = 3
f(2,1) = f(1,3) = f(0+1,2+1) = f(0,f(1,2)) = 1 + f(1,2)
f(1,2) = f(0+1,1+1) = f(0,f(1,1)) = 1 + f(1,1) = 4
f(2,1) = 1 + f(1,2) = 5
f(2,2) = f(1,5)

Puis comme f(1,n) = 1 + f(1,n-1) on arrive à f(2,2) = 3 + f(1,2) = 7

[Dinozzo13]

Ok, je vais continuer tout ça :++: merci à vous deux car j'étais perdu

[Ben314]

Salut,
Si tu veut faire "un peu plus théorique", tu peut regarder :

1) Quel est le premier terme de la suite Un=f(1,n) ? Quelle formule relie U(n+1) à Un ? Qu'en déduit tu ?

2) Quel est le premier terme de la suite Vn=f(2,n) ? Quelle formule relie V(n+1) à Vn ? Qu'en déduit tu ?

[Dinozzo13]

Intéressant, je n'avais pas eu l'idée d'introduire les suites ans un pareil exercice :++:
Mais qu'entends-tu par "quelle formule relie ..." ?
Tu veux parler des trois formules données au début ?

[Ben314]

Si on numérote les trois règles :
R1 :
R2 :
R3 :

Et que l'on note , on a :
grâce à R2 puis R1
grâce à R3 puis R1
Donc la suite , est une suite arithmétique de premier terme et de raison 1.
On en déduit que :
R4 :

Procède de la même façon pour , ...

[Dinozzo13]

Oui, mais je ne vois pas où cela va-t-il nous amener ?

[Ben314]

Ben....
Si tu arrive à exprimer f(2,n) en fonction de n, tu n'auras plus qu'à remplacer n par 2 pour avoir ton résultat !!!!


(c'est pour ça que cette méthode est plus "théorique" : tu démontre bien plus que ce que l'on te demande...)