Oggi dimostrimao il teorema di ricorsione di Kleene. Questo teorema può essere applicato per la costruzione di quine (ovvero programmi che restituiscono in uscita il codice sorgente del programma stesso senza usare funzioni di I/O), per eliminare la ricorsione (le definizioni ricorsive possono essere convertite in definizioni non ricorsive, poichè la nozione di calcolabilità non richiede la ricorsione, vedi MdT, programmi WHILE) e per dimostrare altri concetti utili per la calcolabilità. Inoltre, esistono collegamenti con la logica mamtematica, la teoria dei sistemi che si auto-riproducono e persino con i virus informatici che si auto-replicano.

Teorema di ricorsione (Kleene 2)

Teorema: \(\forall f\) funzione calcolabile (totale) esiste un indice \(n\) tale che \(\varphi_n = \varphi_{f(n)}\) . L’indice \(n\) viene detto punto fisso di \(f.\)

La funzione f trasforma indici in indici e quindi programmi in programmi. Dato un programma \(P_x\) si passa a \(P_{f(x)}\) . Nonostante la trasformazione del programma, la sua semantica non cambia.

Osserviamo che le funzioni calcolabili sono chiuse rispetto alle trasformazioni di indici introdotte dal teorema del parametro (data una funzione calcolabile ottengo sempre una funzione calcolabile).

Dimostrazione:

1. definiamo la funzione calcolabile “diagonale”:
   $$ \psi(u,z)=\varphi_{d(u)}(z) = \begin{cases}\varphi_{\varphi_u(u)}(z)&\text{se}\>\varphi_u(u)\downarrow \\\text{indefinita}&\text{altrimenti}\end{cases} $$
2. Possiamo dimostrare che per il teorema del parametro \(s_m^n\) , la funzione \(d(u)\) è totale e iniettiva.
   • scelgo uno degli indici \(i\) delle macchine che calcolano \(\psi\) , cioè \(\psi(u,z) = \varphi_i(u,z)\) .
   • per il teorema del parametro si ha che \(\varphi_i(u,z) = \varphi_{s(i,u)}(z)\)
   • \(s(i,u)\) dipende solo da u e quindi posso definire \(d(u)=\lambda u.s(i,u) \implies \varphi_i(u,z) = \varphi_{d(u)}(z)\) .
3. La funzione \(f\) calcolabile è data nelle ipotesi del teorema, poichè \(f \circ d\) è calcolabile, posso trovare l’indice \(v\) della funzione calcolabile \(\varphi_v(x)=f(d(x))\) .
4. \(\varphi_v(x)\) è totale in quanto composizione di due funzioni totali, quindi \(\varphi_v(x) \downarrow\) .
5. grazie al punto 1, abbiamo che \(\varphi_{d(v)} = \varphi_{\varphi_v(v)}\)
6. poniamo \(n = d(v)\)
7. possiamo ora dimostrare che n è un punto fisso di f (cioè che \(\varphi_n = \varphi_{f(n)}\) ):

L’iniettività di d è importante nella prima uguaglianza: al variare di n non devo ritrovare più volte la funzione con stesso indice \(\varphi_{d(v)}\).

Proprietà del teorema di ricorsione

Proprietà 1: il punto fisso è calcolabile mediante una funzione totale (iniettiva) \(g\) a partire dall’indice di \(f\)

Dimostrazione: prendo \(h(x)\) calcolabile totale e tale da avere \(\varphi_{h(x)}(n) = \varphi_x(d(n))\) . Allora \(g(x) = d(h(x))\) . Non capisco questa traccia di dimostrazione, ma per il momento questo è quanto.

Proprietà 2: ci sono \(\#(\mathbb{N})\) punti fissi di \(f\)

Dimostrazione: sappiamo che ogni funzione calcolabile totale ha \(\#(\mathbb{N})\) indici. Segue che se ho un punto fisso di f posso trovare \(\#(\mathbb{N})\) funzioni calcolabili totali equivalenti.