Trouver n de la fonction Ackermann

Question

J'essaie de résoudre le problème suivant: Quelle est la plus grande valeur de n pour laquelle A (2, n) peut être représenté comme un entier non signé de 37 bits?

Je sais que les conditions suivantes sont vraies pour la fonction Ackermann:

A(0,n) = n+1 
A(m,0) = A(m-1,1) 
A(m,n) = A(m-1, A(m,n-1)) 

Comment puis-je aller d'ici? On dirait que sans savoir n l'équation devient très longue

Answer 1

Calculer A(2,n) pour quelques valeurs de n; il se développe assez rapidement, il ne devrait donc pas en prendre beaucoup pour obtenir une valeur suffisamment élevée.