Teorema S m n

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

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 teorema 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^m_n(z,y_1,..., y_m)}(x_1 ,..., x_n)
dove \varphi è una funzione parziale.

Conseguenza[modifica | modifica wikitesto]

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

Esempio[modifica | modifica wikitesto]

Il seguente codice Lisp implementa teorema 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)).

Argomenti correlati[modifica | modifica wikitesto]


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