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.

Siano ${\displaystyle n,x,y\in \mathbb {N} }$

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

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

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

Si ha: ${\displaystyle F_{1}(x,y)=F_{1}(0,y)+2^{y}x}$.

• 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