In questa lezione dimostro alcuni teoremi che ci portano alla costruzione della macchina delle macchine: la Macchina di Turing Universale, capace di simulare qualsiasi altra macchina di Turing.

Si tratta di un concetto molto interessante, anche perché ci avvicina ai computer programmabili a cui siamo abituati ai giorni d’oggi. È affascinante constatare che un’invenzione così importante sia stata realizzata solo dopo lo sforzo e l’inventiva di matematici che ne hanno teorizzato e dimostrato l’esistenza teorica. Soltanto con le successive scoperte e miglioramenti tecnologici è stato possibile concretizzare questo modello astratto nel nostro mondo fisico.

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

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.

Argomento diagonale di Cantor generalizzato
Argomento diagonale di Cantor generalizzato

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: 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. 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): 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 ei 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: \(\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 si 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 \(T(µy.T(i,x,y))\) è definita per composizione e µ-ricorsione a partire da una funzione e un predicato primitive ricorsive, quindi è essa stessa una funzione calcolabile in due argomenti i e x ed avrà un indice z, cioè sia \(\varphi_z(i,x) = U(µy.T(i,x,y))\) . Per il teorema di forma normale otteniamo che \(U(µy.T(i,x,y)) = \varphi_i(x)\) . Di conseguenza per transitività dell’uguaglianza ottengo la tesi.

Macchina di Turing Universale

Il teorema di enumerazione garantisce l’esistenza della macchina di Turing Universale \(M_z\) che è in grado di ricevere in input i e x e di simulare la macchina \(M_i\) applicata a x.

A differenza da quanto previsto da Alan Turing, ovvero un esecutore umano delle MdT, grazie al teorema di enumerazione abbiamo una macchina in grado di eseguire qualsiasi algoritmo.

Per comodità descriveremo una Macchina di Turing Universale usando una MdT con 3 nastri semi-infiniti a destra. Vedremo che la macchina a n nastri è del tutto equivalente a una MdT a 1 nastro.

Aggiungiamo inoltre un altro insieme di stati ausiliario \(Q_\star\) e un altro alfabeto ausiliario \(\Sigma_\star\). Questi insiemi sono gli insiemi che verranno utilizzati dalle macchine simulate. Rappresentiamo tutti gli elementi degli insiemi ausiliari come stringhe del monoide \(\{|\}^\star\) mediante una funzione di codifica \(\mathcal{k}\):

$$ k:Q_\star \cup \{h\} \cup \Sigma_\star \cup \{L,R,-\} \mapsto \{|\}^\star $$
$$ \begin{align} h &\mapsto \> | \\ q_i &\mapsto \> |^{i+2} \\ L &\mapsto \> | \\ R &\mapsto || \\ - &\mapsto ||| \\ \sigma_i &\mapsto \> |^{i+4} \end{align} $$

Notiamo che k non è biunivoca, ma lo è quando sappiamo se la stringa che dobbiamo decodificare è uno stato o un simbolo o una direzione. Possiamo ovviare a questo inconveniente separando sul nastro la codifica degli stati, simboli e direzioni con un apposito simbolo c separatore.

A questo punto vogliamo codificare una macchina \(M = (Q,Σ,δ,h)\) . Prima di codificare la macchina definiamo un ordinamento totale degli stati \(Q = \{q_{i1},...,q_{ik}\}\) e i simboli \(Σ = \{σ_{j1},...,σ_{jl}\}\) in modo che \(p ≤ p' \Rightarrow i_p \leq i_{p'} \wedge j_p \leq j_{p'}\) .

Consideriamo l’alfabeto \(\{|,c,d,\#,▷\}\) , ipotizzando che \(\{|,c,d\} \cap (Σ_\star \cup Q_\star) = ∅\) (i simboli |, c e d non sono inclusi nell’alfabeto della macchine simulabili) e ricordando che c è un separatore e codifichiamo ogni quintupla di M così:

$$ \begin{align} &S_{q,p} = c\>κ(q_{ip})\>c\>κ(q)\>c\>κ(σ)\>c\>κ(D)\>c &\text{ se } δ(q_{ip}, σ_{jq}) = (q,σ,D) \end{align} $$

Infine andiamo a codificare anche i casi in cui δ non è definita, ponendo:

$$ \begin{align} &S_{q,p} = c\>κ(q_{ip})\>c\>κ(σ_{jq})\>c\>d\>c\>d\>c\>d\>c &\text{ se } δ(q_{ip}, σ_{jq}) \text{ non è definita} \end{align} $$

Domani vedremo alcuni esempi. A domani.