title: Funzione di Sudan
text: # 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}$ |
  