Fonction de Sudan

Un article de Wikipédia, l'encyclopédie libre.

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

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

[modifier] Définition

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.\,

[modifier] Voir aussi

Autres langues