fonction d’Ackermann

ALGEBRE
ARITHMETIQUE
INFORMATIQUE

La fonction de Ackermann est une fonction récursive de N² dans N ; sous sa forme actuelle elle a été présentée par Rosza Péter et Raphael Robinson après la deuxième guerre mondiale mais son prototype sous forme de fonction à 3 variables a été construit par deux étudiants d’Hilbert vers 1920 : Wihlem Ackermann et Gabriel Sudan.
Elle est définie récursivement de la façon suivante :
A(m,n) = m + 1 si m=0
A(m,n) = A(m-1, 1 ) si m>0 et n=0
A(m,n) = A(m-1, A(m, n-1) ) si m >0 et n > 0.

Cette fonction croit très rapidement ainsi :
A(4,1) = 65533 et A(4,2) = 2 ⁶⁵⁵³³ – 3.
Cette fonction est importante dans la théorie de la calculabilité.