title: Teorema S m n
text: # Teorema S m n
  
  In teoria della ricorsione, il teorema $S_{n}^{m}$ è un risultato di base sugli algoritmi, astrattamente chiamati numerazione di Gödel, fornito originariamente da Stephen Cole Kleene.
  
  Informalmente, il teorema dice che, dato un programma che prenda in entrata m+n variabili, esiste un algoritmo ricorsivo che fornisce in uscita un programma di n variabili che fornisce gli stessi risultati del primo e che codifica le altre m variabili.
  
  ## Descrizione
  
  Sia una funzione di m+n variabili il cui numero di Gödel sia z
  
      $\varphi _{z}(x_{1},...,x_{n},y_{1},...,y_{m})$
  
  Si dividono le variabili della funzione in due blocchi dove il primo rimane variabile e il secondo costante. Esiste una funzione ricorsiva primitiva $S_{n}^{m}$ di m+1 variabili (detto altrimenti: "Esiste una procedura generale che prende in ingresso z e $y_{1},...,y_{m}$") e fornisce il numero di Gödel $g_{n}$ di una procedura delle restanti variabili che dia lo stesso risultato.
  
      $\varphi _{z}(x_{1},...,x_{n},y_{1},...,y_{m})\simeq \varphi _{S_{n}^{m}(z,y_{1},...,y_{m})}(x_{1},...,x_{n})$
  
  dove $\varphi$ è una funzione parziale.
  
  ### Conseguenza
  
  Se un sistema di funzioni soddisfa il Teorema Smn allora tale sistema è Turing completo.
  
  ## Esempio
  
  Il seguente codice Lisp implementa teorema $S_{1}^{1}$.
  
  Ad esempio, (s11 '(lambda (x y) (+ x y)) 3) valuta a (lambda (y) ((lambda (x y) (+ x y)) 3 y)).
  
  