Fonction de Sudan

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En calculabilité, la fonction de Sudan est un exemple de fonction récursive mais non récursive primitive. C'est aussi le cas de la fonction d'Ackermann, plus connue.

Elle fut conçue en 1927 par le mathématicien roumain Gabriel Sudan, élève de David Hilbert.

Définition[modifier | modifier le code]

F _0 (x, y) = x+y,\,
F _{n+1} (x, 0) = x, \  n \ge 0\,
F _{n+1} (x, y+1) = F _n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), \ n\ge 0.\,

Voir aussi[modifier | modifier le code]