Oggi andiamo a dimostrare alcuni teoremi che caratterizzano le funzioni calcolabili. Dimostreremo che esistono infinite numerabili funzioni calcolabili e che, nonostante ciò, esistono funzioni non calcolabili.

Questi teoremi ci consentiranno di arrivare ad un risultato molto importante, ovvero che può esistere una MdT universale, in grado di simulare tutte le altre.

Teoremi sulle funzioni

Cardinalità delle funzioni calcolabili

Teorema: le funzioni calcolabili sono \(\#(\mathbb{N})\) ; inoltre anche le funzioni calcolabili totali sono \(\#(\mathbb{N})\) .

Dimostrazione: costruisci \(\#(\mathbb{N}) \text{ MdT } M_i\) che dal nastro vuoto scrivono le funzioni costanti \(|^i\) e si arrestano. Le MdT si possono enumerare e questo lo si può intuire grazie alla codifica delle MdT che avevamo introdotto qualche giorno fa. Essendo enumerabili, le MdT non sono più di \(\#(\mathbb{N})\) ed avendone costruite almeno \(\#(\mathbb{N})\) diverse, possiamo concludere che sono esattamente \(\#(\mathbb{N})\) .

Esistenza di funzioni non calcolabili

Teorema: Esistono funzioni non calcolabili e sono molte di più di quelle calcolabili.

Dimostrazione: con una costruzione simile a quella di Cantor (vedi insieme di Cantor, teorema di Cantor e argomento diagonale di Cantor e questo video di Veritasium) si vede che \(\#\{f : \mathbb{N} \mapsto \mathbb{N}\} = 2^{\#(\mathbb{N})}\) e quindi dato che le funzioni calcolabili totali sono \(\#(\mathbb{N})\) , mentre tutte le funzioni possibili sono “di più”, ecco che abbiamo dimostrato l’esistenza di funzioni non calcolabili.

Indici di Macchine e funzioni

Avevamo detto che Gödel definì una codifica iniettiva e surgettiva (mentre noi ne abbiamo visto solo una iniettiva) per le MdT. Data una enumerazione effettiva, indichiamo con \(\varphi_i^{(n)} \) la funzione parziale in n variabile che la macchina \(M_i\) calcola e chiameremo \(i\) indice della macchina. Notiamo che per \(i \ne j\) è possibile che \(\varphi_i = \varphi_j\) , mentre sicuramente \(M_i \ne M_j\) , cioè è ben possibile che due macchine con indici diversi calcolino la stessa funzione!

Teorema del padding lemma

Teorema: ogni funzione calcolabile \(\varphi_x \text{ ha } \#(\mathbb{N})\) indici. Inoltre \(\forall x\) si può costruire mediante una funzione ricorsiva primitiva, un insieme infinito \(A_x\) di indici tale che:

$$ \forall y \in A_x . \varphi_y = \varphi_x $$

Dimostrazione: \(\forall M_x \text{ con } Q = \{q_0,...,q_k\}\) , ottengo la prima macchina \(M_{x_1} \text{ con } x_1 \in A_x\) aggiungendo lo stato \(q_{k+1} \notin Q\) e la quintupla \((q_{k+1},\#,q_{k+1},\#,-)\) e procedo ottenendo le altre infinite macchine aggiungendo uno a k ad ogni iterazione. □

In altre parole aggiungo alla macchina stati non raggiungibili che non fanno niente. In questo modo è ovvio che la macchina calcola la stessa funzione, ma gli indici delle due macchine sono diversi. In altre parole la semantica della macchina M o del programma non è cambiata, ma è cambiata la sua sintassi. Una enumerazione effettiva può dipendere solo dalla sintassi del programma.

Tuttavia il prossimo teorema ci dirà che fra tutti i possibili algoritmi ce n’è uno privilegiato, che ha una forma speciale e quindi ogni funzione avrà la sua rappresentazione privilegiata.

Teorema di forma normale (Kleene 1)

Teorema: esistono un predicato \(T(i,x,y)\) e una funzione \(U(y)\) calcolabili totali tali che \(\forall i,x.\varphi_i(x) = U(\mu y.T(i,x,y))\) . Inoltre T e U sono primitive ricorsive.

Dimostrazione: il predicato \(T(i,x,y)\) viene anche chiamato predicato di Kleene che è vero se e solo se y è la codifica di una computazione terminante di \(M_i\) con dato iniziale x.

T è intuitivamente calcolabile: decodifico la computazione terminante codificata in y (una sequenza finita di passi di computazione), recupero la macchina \(M_i\) ed inizio ad eseguirla passo per passo controllando che i passi eseguiti corrispondano alla computazione decodificata. Se le due computazioni combaciano e terminano allora restituisco vero, altrimenti falso. Attenzione: non posso eseguire direttamente \(M_i\) e vedere se termina, poiché \(M_i\) potrebbe non terminare!

Anche U è intuitivamente calcolabile: comincio a scandire tutti i possibili valori di y e non appena trovo che T restituisce vero (ovvero 0), allora so che \(U(y) = z\) .

Essendo sia T che U intuitivamente calcolabili, per la tesi di Church-Turing posso affermare che T e U sono calcolabili. Inoltre T e U terminano sempre, quindi sono due funzioni totali. Inoltre T e U sono ricorsive primitive perché lo sono le codifiche utilizzate e i controlli effettuati. □

Una conseguenza del teorema di forma normale è che ogni funzione calcolata da una MdT ammette una definizione µ-ricorsiva.

Possiamo dedurre i seguenti corollari:

• Le funzioni T-calcolabili sono µ-ricorsive.
• (lemma) Le funzioni µ-calcolabili sono T-calcolabili.
• (teorema) Una funzione è T-calcolabile se e solo se è µ-calcolabile.
• Ogni funzione calcolabile parziale può essere ottenuta da due funzioni primitive ricorsive e una sola applicazione dell’operatore µ.

Teorema di enumerazione

Teorema: \(\exists z . \forall i,x . \varphi_z(i,x) = \varphi_i(x)\) . Esiste una funzione calcolabile parziale con indice z e argomenti i e x che è in grado di calcolare la funzione con indice i e argomento x.

Dimostrazione: intuitivamente \(M_z\) recupera la descrizione di \(M_i\) e la applica ad \(x\) .
Più formalmente: la funzione definita nel teorema di forma normale \(U(\mu y.T(i,x,y))\) è definita per composizione e µ-ricorsione a partire da una funzione e un predicato primitivo ricorsivo, quindi è essa stessa una funzione calcolabile in due argomenti i e x ed avrà un indice z, cioè sia \(\varphi_z(i,x) = U(\mu y.T(i,x,y))\) . Per il teorema di forma normale otteniamo che \(U(\mu y.T(i,x,y)) = \varphi_i(x)\) . Di conseguenza per transitività dell’uguaglianza ottengo la tesi \((\varphi_z(i,x) = \varphi_i(x))\) . □