Teorema S m n

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

In teoria della ricorsione, il teorema ${\displaystyle 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.

Sia una funzione di m+n variabili il cui numero di Gödel sia z

${\displaystyle \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 ${\displaystyle S_{n}^{m}}$ di m+1 variabili (detto altrimenti: "Esiste una procedura generale che prende in ingresso z e ${\displaystyle y_{1},...,y_{m}}$") e fornisce il numero di Gödel ${\displaystyle g_{n}}$ di una procedura delle restanti variabili che dia lo stesso risultato.

${\displaystyle \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 ${\displaystyle \varphi }$ è una funzione parziale.

Se un sistema di funzioni soddisfa il Teorema Smn allora tale sistema è Turing completo.

Il seguente codice Lisp implementa teorema ${\displaystyle S_{1}^{1}}$.

(defun s11 (f x)
   (list 'lambda '(y) (list f x 'y)))

Ad esempio, (s11 '(lambda (x y) (+ x y)) 3) valuta a (lambda (y) ((lambda (x y) (+ x y)) 3 y)).

• Punto fisso
• Teorema di ricorsione di Kleene
• Valutazione parziale

• (EN) Eric W. Weisstein, Teorema S m n, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica