Funzione di Sudan
# Funzione di Sudan

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 $n,x,y\in \mathbb {N}$

$F_{0}(x,y)=x+y,$

$F_{n+1}(x,0)=x,$

$F_{n+1}(x,y+1)=F_{n}(F_{n+1}(x,y),F_{n+1}(x,y)+y+1).$

## Tabella dei valori

Valori di $F_0(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 |

Valori di $F_1(x,$ y)(OEIS:A260003) :

| 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: $F_{1}(x,y)=F_{1}(0,y)+2^{y}x$.

Valori di $F_2(x,$ y)(OEIS:A260004) :

| y\x | 0 | 1 | 2 | 3 | 4 | 5 |
| - | - | - | - | - | - | - |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | 8 | 27 | 74 | 185 | 440 |
| 2 | 19 | $F_1(8,$ 10) = 10228 | $F_1(27,$ 29) ≈ 1.55 $×10^{10}$ | $F_1(74,$ 76) ≈ 5.74 $×10^{24}$ | $F_1(185,$ 187) ≈ 3.67 $×10^{58}$ | $F_1(440,$ 442) ≈ 5.02 $×10^{135}$ |
