Teorema di Ricursione o di Kleene

Teorema Sia data una enumerazione delle funzioni , sia g(z, x1, . . . , xn) una funzione
allora esiste un intero k tale che

g(k, x1, . . . , xn) = ϕk⁽ⁿ⁾ (x1, . . . , xn)

Dimostrazione Sia s1 n la funzione definita dal teorema s-1-n, ovvero la funzione che parametrizza le funzioni di n + 1 argomenti in funzioni di n argomenti. La funzione cos`ı definita g(s¹_n(v, v), x1, . . . , xn)

`e una funzione T-Calcolabile dipendente dalle variabili v, x1, . . . , xn. Poich`e la funzione s¹_n e la funzione g sono funzioni calcolabili per ipotesi, esiste un indice z0 della enumerazione delle funzioni T-Calcolabili tale che:

g(s¹_n(v, v), x1, . . . , xn) = ϕz0(v, x1, . . . , xn)

Applicando il teorema s-1-n alla funzione ϕz0, si ottiene la seguente relazione:

ϕz0(v, x1, . . . , xn) = ϕs¹_n(z0,v)(x1, . . . , xn)

Supponiamo che v = z0 e k = s¹_n(z0, z0).

Allora:

g(k, x1, . . . , xn) poich`e k = s¹_n(z0, z0)

= g(s¹_n(z0, z0), x1, . . . , xn) poich`e g(s¹_n(v, v), x1, . . . , xn) = ϕz0(v, x1, . . . , xn)

= ϕz0(z0, x1, . . . , xn) applicando il teorema s-1-n

= ϕs¹_n(z0,z0)(x1, . . . , xn) poich`e k = s¹_n(z0, z0)

= ϕk(x1, . . . , xn)

Nella versione appena dimostrata, il teorema di ricursione permette di definire una funzione ϕ^_k(n) di indice k e n argomenti in termini di una codifica del suo stesso programma:

ϕ_k⁽ⁿ⁾ (x1, . . . , xn) = g(k, x1, . . . , xn)