Funzione di Sudan
Vai alla navigazione
Vai alla ricerca
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[modifica | modifica wikitesto]
Siano
Tabella dei valori[modifica | modifica wikitesto]
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 |
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 |
Si ha: .
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 ×1010 | F1(74, 76) ≈ 5.74 ×1024 | F1(185, 187) ≈ 3.67 ×1058 | F1(440, 442) ≈ 5.02 ×10135 |
Bibliografia[modifica | modifica wikitesto]
- 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.