Macchina di Turing e calcolabilità

Se cerchi «cos’è la macchina di Turing» o «come funziona il problema della fermata», sei probabilmente in quinta e il tuo prof di informatica è arrivato alla teoria della computazione. Nel quinto anno del liceo scientifico (opzione scienze applicate, due ore a settimana) questa parte si fa di solito nel primo periodo o a cavallo del secondo, accanto a calcolo numerico e reti; l’ordine e il mese esatto cambiano da scuola a scuola, e non tutte la trattano a fondo. Se in classe è già partita, la verifica scritta o l’interrogazione cadono verosimilmente fra qualche settimana. L’argomento torna anche al colloquio di maturità e, se andrai a ingegneria o informatica, in Algoritmi o Fondamenti di informatica.

Qui trovi la definizione precisa della macchina, un esempio completo da ricopiare, il problema della fermata dimostrato con calma e tre esercizi svolti. Un’avvertenza: su questo argomento non c’è ancora un simulatore sul sito, quindi il materiale di prova sono gli esercizi qui sotto.

Algoritmo e «calcolabile»

Un algoritmo è una sequenza finita di istruzioni non ambigue che, per ogni ingresso valido, porta a un risultato in un numero finito di passi. La ricetta con «q.b.» non lo è; l’ordinamento per scambi sì (lo trovi in bubble, selection e insertion sort).

Un problema è calcolabile (se la risposta è sì/no, decidibile) quando esiste un algoritmo che lo risolve per tutti gli ingressi e termina sempre. La domanda di Turing era: esistono problemi ben posti per cui un algoritmo del genere non può esistere, comunque veloce sia il computer? Per rispondere bisognava prima dire con precisione cosa sia «un algoritmo». Da qui la macchina.

La macchina di Turing, definita con precisione

Alan Turing la propose nel 1936 come modello minimo di calcolo. Ha cinque ingredienti.

Il nastro: celle in sequenza, illimitate. Ogni cella contiene un simbolo; quelle mai scritte contengono il simbolo vuoto, che indico con _.
L’alfabeto: l’insieme finito dei simboli ammessi. Nei nostri esercizi 0, 1 e _.
La testina: legge e scrive una cella alla volta e si sposta a destra (R), a sinistra (L) o resta ferma (S).
Gli stati: un insieme finito $Q$ , con uno stato iniziale $q_{0}$ e almeno uno stato di arresto. È l’unica memoria interna della macchina.
La funzione di transizione, cioè il programma:

δ (q, a) = (q^{'}, b, D)

Si legge: nello stato $q$ , con la testina che legge $a$ , la macchina scrive $b$ , si sposta in direzione $D$ e passa allo stato $q^{'}$ . In forma completa:

M = (Q, Σ, Γ, δ, q_{0}, F)

dove $Σ$ è l’alfabeto di ingresso, $Γ = Σ \cup {_}$ quello del nastro e $F$ gli stati di arresto. Il calcolo parte con l’ingresso sul nastro e la testina sulla sua prima cella; a ogni passo si applica la regola della coppia (stato, simbolo letto); si finisce entrando in uno stato di arresto. Se per una coppia non esiste nessuna regola, la macchina si ferma comunque.

Con la macchina si possono fare due cose: calcolare una funzione (il risultato è ciò che resta sul nastro all’arresto) oppure decidere un linguaggio (due stati di arresto, accettazione e rifiuto, per rispondere «sì» e «no»). Gli esercizi usano entrambe.

Esempio completo: incrementare un numero binario

Voglio una macchina che aumenti di 1 un numero binario. Uso l’addizione in colonna: parto dall’ultima cifra; se è 1 diventa 0 e il riporto passa a sinistra; se è 0 diventa 1 e ho finito; se esco dal numero a sinistra (erano tutti 1) scrivo un 1 davanti. Per raggiungere l’ultima cifra la testina deve prima scorrere a destra. Servono tre stati: $q_{0}$ (scorro a destra fino alla prima cella vuota), $q_{1}$ (torno indietro con il riporto), $q_{f}$ (arresto).

Stato	Letto	Scrive	Muove	Nuovo stato
$q_{0}$	`0`	`0`	R	$q_{0}$
$q_{0}$	`1`	`1`	R	$q_{0}$
$q_{0}$	`_`	`_`	L	$q_{1}$
$q_{1}$	`1`	`0`	L	$q_{1}$
$q_{1}$	`0`	`1`	S	$q_{f}$
$q_{1}$	`_`	`1`	S	$q_{f}$

La tabella copre ogni caso possibile: in $q_{0}$ si può leggere 0, 1 o vuoto; in $q_{1}$ 1, 0 o vuoto (il riporto che esce dal numero).

Traccia su 1011

A ogni passo scrivo la configurazione: stato, nastro e posizione della testina (fra parentesi quadre). L’ingresso è $101 1_{2} = 11$ ; mi aspetto $110 0_{2} = 12$ .

Passo	Stato	Nastro	Regola applicata
0	$q_{0}$	`[1]011`	$(q_{0}, 1) \to (1, R, q_{0})$
1	$q_{0}$	`1[0]11`	$(q_{0}, 0) \to (0, R, q_{0})$
2	$q_{0}$	`10[1]1`	$(q_{0}, 1) \to (1, R, q_{0})$
3	$q_{0}$	`101[1]`	$(q_{0}, 1) \to (1, R, q_{0})$
4	$q_{0}$	`1011[_]`	$(q_{0},_) \to (_, L, q_{1})$
5	$q_{1}$	`101[1]`	$(q_{1}, 1) \to (0, L, q_{1})$
6	$q_{1}$	`10[1]0`	$(q_{1}, 1) \to (0, L, q_{1})$
7	$q_{1}$	`1[0]00`	$(q_{1}, 0) \to (1, S, q_{f})$
8	$q_{f}$	`1[1]00`	arresto

Controllo riga per riga. Nei passi 0-3 la testina attraversa le quattro cifre senza modificarle. Al passo 4 legge il vuoto, torna indietro di una cella e passa a $q_{1}$ , sull’ultima cifra. Al passo 5 quel 1 diventa 0 (nastro 1010) e il riporto sale; al passo 6 anche la terza cifra, 1, diventa 0 (nastro 1000); al passo 7 la seconda cifra, 0, diventa 1 e la macchina si ferma con nastro 1100, cioè 12. Giusto.

Due prove sui casi limite. Su 0: $q_{0}$ scorre, $q_{1}$ legge 0 e scrive 1; risultato 1. Su 111: il riporto azzera tutte le cifre, la testina esce a sinistra, legge il vuoto e la riga $(q_{1},_)$ scrive un 1 davanti; risultato 1000, cioè $7 + 1 = 8$ .

Prima di andare avanti copri la tabella e prova a riscriverla da solo. Per gli altri argomenti scientifici del liceo la categoria è quella delle simulazioni per il liceo; qui, come detto, la prova sei tu con carta e penna.

La macchina di Turing universale

Una macchina come quella sopra fa una sola cosa. Turing mostrò che se ne può costruire una universale $U$ che prende come ingresso la descrizione di un’altra macchina $M$ (la sua tabella, scritta come stringa sul nastro) insieme a un dato $x$ , e simula $M$ su $x$ . È l’idea del computer a programma memorizzato: il programma è un dato come gli altri. La dimostrazione sulla fermata si regge proprio su questo, cioè sul fatto che un programma può essere dato in pasto a un altro programma.

La tesi di Church-Turing

Negli anni Trenta furono proposti modelli di calcolo molto diversi fra loro (la macchina di Turing, il lambda-calcolo di Church, le funzioni ricorsive) e si dimostrò che calcolano esattamente le stesse funzioni. Da qui la tesi di Church-Turing: ogni funzione calcolabile con un procedimento meccanico effettivo è calcolabile da una macchina di Turing.

In verifica fai attenzione: non è un teorema. Un teorema si dimostra, e qui non si può, perché «procedimento effettivo» è un concetto intuitivo, non una definizione matematica. È una tesi sostenuta da un’evidenza forte: nessuno ha mai trovato un procedimento che i modelli formali non sappiano riprodurre. Scrivere «la tesi è stata dimostrata» è un errore frequente.

Il problema della fermata

Dati un programma $P$ e un dato $x$ , stabilire se $P$ termina su $x$ oppure gira per sempre. Sembra facile («lo lancio e guardo»), ma funziona solo quando termina: se dopo un’ora gira ancora, non so se finirà fra un minuto o mai. Turing dimostrò che nessun algoritmo risolve questo problema in generale. La dimostrazione, un passo alla volta.

Passo 1, l’ipotesi. Suppongo per assurdo che esista una funzione H(programma, dato) che termina sempre e restituisce True se programma(dato) termina, False altrimenti.

Passo 2, la costruzione. Con H scrivo un programma D che prende in ingresso un programma:

def D(programma):
    if H(programma, programma):   # H dice: "programma(programma) termina"
        while True:               # allora D entra in un ciclo infinito
            pass
    else:                         # H dice: "non termina"
        return                    # allora D termina subito

D fa il contrario di ciò che H prevede per un programma dato a sé stesso.

Passo 3, la domanda decisiva. Cosa succede con D(D)? È lecito dare a D la propria descrizione, perché un programma è un testo, quindi un dato.

Se D(D) termina, H(D, D) ha risposto True e per costruzione D cicla all’infinito. Contraddizione.
Se D(D) non termina, H(D, D) ha risposto False e per costruzione D termina subito. Contraddizione.

Passo 4, la conclusione. Entrambi i casi portano a una contraddizione. L’unica ipotesi fatta è l’esistenza di H, quindi H non può esistere: il problema della fermata è indecidibile. Questo non vuol dire che nessun programma sia analizzabile; per molti programmi concreti si capisce se terminano. Vuol dire che nessun algoritmo lo stabilisce per tutti i programmi e tutti i dati.

Decidibile e semidecidibile

Un problema è decidibile se esiste una macchina che termina sempre, rispondendo correttamente sì o no. È semidecidibile (nei libri anche «riconoscibile» o «ricorsivamente enumerabile») se esiste una macchina che, quando la risposta è sì, termina e lo dice, ma quando è no può non terminare mai. La fermata è semidecidibile: basta simulare P su x e rispondere sì appena termina. Non è decidibile, come abbiamo appena dimostrato.

E la complessità? P e NP in due righe

Calcolabilità e complessità rispondono a domande diverse: la prima chiede se esiste un algoritmo, la seconda quanto costa. P raccoglie i problemi decidibili in tempo polinomiale nella dimensione dell’ingresso; NP quelli di cui una soluzione data si può verificare in tempo polinomiale. Se le due classi coincidano è un problema ancora aperto. Il calcolo del costo è in complessità e notazione O-grande; anche la crittografia a chiave pubblica si regge sulla difficoltà pratica di certi problemi, non sulla loro indecidibilità (Cesare, Vigenère e RSA).

Gli errori tipici

Confondere la macchina di Turing con un computer reale. La macchina è un modello matematico con nastro illimitato; un computer ha memoria finita, processore e tempi di esecuzione. La macchina serve a dire cosa è possibile in linea di principio.
Credere che «non calcolabile» voglia dire «lento». Un problema che richiede anni di calcolo è calcolabile, perché l’algoritmo esiste e termina. Non calcolabile significa che nessun algoritmo esiste, con qualunque tempo a disposizione.
Dimenticare lo stato di arresto, o lasciare la tabella incompleta. Una macchina che non si ferma mai, o che in qualche caso non sa cosa fare, non è un programma.
Scrivere che la tesi di Church-Turing è un teorema.
Saltare i casi limite. Per l’incremento, 0 e 111.

Esercizi svolti

Esercizio 1: incremento binario

Costruisci la tabella di una macchina di Turing che incrementa di 1 un numero binario e traccia l’esecuzione su 1011.

È l’esempio sopra: sei righe, stati $q_{0}$ , $q_{1}$ , $q_{f}$ , e nove configurazioni (passi 0-8) da 1011 a 1100, cioè da 11 a 12. Controllo su 1101: la testina scorre fino al vuoto e torna; l’ultima cifra 1 diventa 0 con riporto; la cifra precedente, 0, diventa 1 e la macchina si ferma. Nastro finale 1110, cioè $13 + 1 = 14$ .

Esercizio 2: parità della lunghezza

Una stringa è fatta solo di simboli 1. Costruisci una macchina che accetta se la lunghezza è pari e rifiuta se è dispari; traccia l’esecuzione su 1111 e su 111.

La testina scorre senza modificare niente e lo stato ricorda se i 1 letti finora sono in numero pari o dispari. Quattro stati: $q_{p}$ (iniziale: pari, zero compreso), $q_{d}$ (dispari), $q_{A}$ (arresto, accetto), $q_{R}$ (arresto, rifiuto).

Stato	Letto	Scrive	Muove	Nuovo stato
$q_{p}$	`1`	`1`	R	$q_{d}$
$q_{d}$	`1`	`1`	R	$q_{p}$
$q_{p}$	`_`	`_`	S	$q_{A}$
$q_{d}$	`_`	`_`	S	$q_{R}$

Passo	Su `1111`: stato e nastro	Su `111`: stato e nastro
0	$q_{p}$ , `[1]111`	$q_{p}$ , `[1]11`
1	$q_{d}$ , `1[1]11`	$q_{d}$ , `1[1]1`
2	$q_{p}$ , `11[1]1`	$q_{p}$ , `11[1]`
3	$q_{d}$ , `111[1]`	$q_{d}$ , `111[_]`
4	$q_{p}$ , `1111[_]`	$q_{R}$ , `111[_]` (rifiuto)
5	$q_{A}$ , `1111[_]` (accetto)

1111 arriva a $q_{A}$ (4 è pari), 111 a $q_{R}$ (3 è dispari). Sulla stringa vuota $q_{p}$ legge subito il vuoto e accetta, coerente con il fatto che 0 è pari. Qui la memoria della macchina è tutta nello stato: due stati bastano a contare «pari o dispari» senza scrivere nulla.

Esercizio 3: perché la fermata non è decidibile

Spiega perché non esiste un algoritmo che decide se un programma termina su un dato ingresso.

Come lo scriverei in verifica: «Dimostro per assurdo. Suppongo che esista H(P, x) che termina sempre e dice se $P$ termina su $x$ . Costruisco D(P): se H(P, P) dice che $P$ termina su sé stesso, D entra in un ciclo infinito; altrimenti termina subito. Considero D(D). Se termina, H(D, D) ha detto True e D per costruzione cicla: contraddizione. Se non termina, H(D, D) ha detto False e D per costruzione termina: contraddizione. L’unica ipotesi è l’esistenza di H, quindi H non esiste: il problema è indecidibile, pur essendo semidecidibile.»

Chi corregge guarda l’ipotesi dichiarata, la costruzione di D, entrambi i rami della contraddizione e la frase finale che attribuisce l’assurdo a H. Spesso manca un ramo, oppure la conclusione.

Come studiarlo

Ricopia a mano la tabella dell’incremento, chiudi tutto, riscrivila da zero e traccia l’esecuzione su un ingresso nuovo. Per la teoria, spiega la dimostrazione della fermata a voce, senza guardare: è il metodo che consiglio a chi prepara l’orale. Se vuoi un argomento affine, la ricorsione, dove un programma richiama sé stesso come nella dimostrazione della fermata, è in fattoriale, Fibonacci e MCD.

Se vuoi una mano su teoria della computazione, programmazione o sul resto di informatica, la diagnosi gratuita è su contatti. Per allenarti sulle altre materie scientifiche, le simulazioni per il liceo restano il punto di partenza.

Macchina di Turing e calcolabilità: cosa serve capire