Nella teoria della calcolabilità, la funzione di Sudan è una funzione ricorsiva totale non primitiva.
La funzione era la prima che confutò la credenza che le funzioni ricorsive fossero necessariamente primitive. La scoperta è attribuita al matematico Gabriel Sudan, uno studente di David Hilbert nel 1927, qualche anno prima di quella della più nota funzione di Ackermann.
Definizione Siano
Tabella dei valori +Valori di F0(x, y)y\x0123450012345112345622345673345678445678955678910667891011 +Valori di F1(x, y)(OEIS:A260003)y\x0123456001234561135791113248121620242831119273543515942642587490106122557891211531852172496120184248312376440504 Si ha: . +Valori di F2(x, y)(OEIS:A260004)y\x01234500123451182774185440219F1(8, 10) = 10228F1(27, 29) ≈ 1.55 ×1010F1(74, 76) ≈ 5.74 ×1024F1(185, 187) ≈ 3.67 ×1058F1(440, 442) ≈ 5.02 ×10135
Bibliografia Cristian Calude, Solomon Marcus et Ionel Tevy, The first example of a recursive function which is not primitive recursive, Historia Mathematica 6, 1979, no. 4, 380–384 doi:10.1016/0315-0860(79)90024-7. Sudan function - Jump up Bull. Math. Soc. Roumaine Sci. 30, 1927, 11 - 30; Jbuch 53, 171.
Sudan