Teorema S mn

În teoria recursivității , teorema $S_{n}^{m}$ ${\ displaystyle S_ {n} ^ {m}}$ $S_ {n} ^ {m}$ este un rezultat de bază al algoritmilor , numit în mod abstract numerotarea Gödel , furnizat inițial de Stephen Cole Kleene .

În mod informal, teorema spune că, având în vedere un program care ia în m + n variabile, există un algoritm recursiv care produce un program de n variabile care dă aceleași rezultate ca prima și care codifică celelalte m variabile.

Descriere

Fie o funcție a variabilelor m + n al căror număr Gödel este z

\varphi _{z}(x_{1},...,x_{n},y_{1},...,y_{m})

{\ displaystyle \ varphi _ {z} (x_ {1}, ..., x_ {n}, y_ {1}, ..., y_ {m})}

\ varphi_z (x_1, ..., x_n, y_1, ..., y_m)

Variabilele funcției sunt împărțite în două blocuri în care primul rămâne variabil și al doilea constant. Există o funcție recursivă primitivă $S_{n}^{m}$ ${\ displaystyle S_ {n} ^ {m}}$ $S_ {n} ^ {m}$ a m +1 variabile (cu alte cuvinte: "Există o procedură generală care ia z și ca intrare $y_{1},...,y_{m}$ ${\ displaystyle y_ {1}, ..., y_ {m}}$ $y_1, ..., y_m$ ") și dă numărul Gödel $g_{n}$ ${\ displaystyle g_ {n}}$ $g_ {n}$ a unei proceduri a variabilelor rămase care dă același rezultat.

\varphi _{z}(x_{1},...,x_{n},y_{1},...,y_{m})\simeq \varphi _{S_{n}^{m}(z,y_{1},...,y_{m})}(x_{1},...,x_{n})

{\ 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})}

\ varphi_z (x_1, ..., x_n, y_1, ..., y_m) \ simeq \ varphi_ {S ^ m_n (z, y_1, ..., y_m)} (x_1, ..., x_n)

unde este $\varphi$ ${\ displaystyle \ varphi}$ $\ varphi$ este o funcție parțială.

Consecinţă

Dacă un sistem de funcții îndeplinește teorema Smn, atunci acest sistem este complet Turing.

Exemplu

Următorul cod Lisp implementează teorema $S_{1}^{1}$ ${\ displaystyle S_ {1} ^ {1}}$ $S_ {1} ^ {1}$ .

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

De exemplu, (s11 '(lambda (xy) (+ xy)) 3) evaluează la (lambda (y) ((lambda (xy) (+ xy)) 3 y)) .

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică