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

F 0 ( x , y ) = x + y , {\displaystyle F_{0}(x,y)=x+y,}

F n + 1 ( x , 0 ) = x , {\displaystyle 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 ) . {\displaystyle 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 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
Valori di F1(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 {\displaystyle F_{1}(x,y)=F_{1}(0,y)+2^{y}x} .

Valori di F2(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 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

  • 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.
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica