En la teoria de la computació, la funció de Sudan és un exemple d'una funció recursiva, però no primitiva recursiva. Això també és cert per la més coneguda funció d'Ackermann. La funció de Sudan va ser la primera funció que va publicar aquesta propietat.
Va ser descoberta (i publicada)Bull. Math. Soc. Roumaine Sci. 30 (1927), 11 - 30; Jbuch 53, 171 el 1927 per Gabriel Sudan, un matemàtic romanès que era estudiant de David Hilbert.
Definició
Taules de valors +Valors de F0(x, y) y\x 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 6 2 2 3 4 5 6 7 3 3 4 5 6 7 8 4 4 5 6 7 8 9 5 5 6 7 8 9 10 6 6 7 8 9 10 11
+Valors de F1(x, y) y\x 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 3 5 7 9 11 13 2 4 8 12 16 20 24 28 3 11 19 27 35 43 51 59 4 26 42 58 74 90 106 122 5 57 89 121 153 185 217 249 6 120 184 248 312 376 440 504
En general, F1(x, y) és igual a F1(0, y) + 2y x.
+Valors de F₂(x, y) y\x 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 8 27 74 185 440 2 19 F1(8, 10) = 10228 F1(27, 29) ≈ 1.55 F1(74, 76) ≈ 5.74 F1(185, 187) ≈ 3.67 F1(440, 442) ≈ 5.02
Referències
Bibliografia
Enllaços externs OEIS: A260003, A260004
Categoria:Computabilitat Categoria:Funcions usades en la teoria de nombres Categoria:Informàtica teòrica