Gli automi finiti hanno memoria costante, gli automi a pila una memoria accessibile solo dalla cima. La macchina di Turing elimina queste restrizioni: dispone di un nastro illimitato che può leggere e scrivere in qualsiasi posizione, spostandosi a sinistra e a destra. Con questo modello si definisce che cosa significa, in senso matematico, che un problema è risolvibile da un algoritmo. In questo articolo la tratto come oggetto formale, lasciando da parte la storia.
Gli ingredienti
Una macchina di Turing (deterministica, a un nastro) è una settupla (Q, Σ, Γ, δ, q₀, q_acc, q_rif):
- Q è l'insieme finito degli stati;
- Σ è l'alfabeto di input, che non contiene il simbolo blank ⊔;
- Γ è l'alfabeto del nastro, con Σ ⊆ Γ e ⊔ ∈ Γ;
- δ: Q × Γ → Q × Γ × {S, D} è la funzione di transizione;
- q₀ è lo stato iniziale;
- q_acc e q_rif sono lo stato di accettazione e quello di rifiuto, distinti.
La transizione δ(q, a) = (r, b, D) si legge: «nello stato q, se la testina legge a, scrivi b al posto di a, spostati a destra ed entra nello stato r». S indica uno spostamento a sinistra; se la testina è già sulla prima cella, resta ferma.
Come parte e come si ferma
All'inizio l'input w occupa le prime celle del nastro, tutte le altre contengono il blank, la testina è sulla prima cella e lo stato è q₀. La macchina applica δ un passo alla volta.
Il calcolo si ferma solo se si entra in q_acc o in q_rif. Ci sono quindi tre esiti possibili:
- la macchina accetta (raggiunge q_acc);
- la macchina rifiuta (raggiunge q_rif);
- la macchina non si ferma mai.
Il terzo esito è la grande novità rispetto agli automi finiti, che terminano sempre dopo aver letto l'input. È proprio questa possibilità a rendere le macchine di Turing così potenti e, allo stesso tempo, a generare problemi indecidibili.
Configurazioni
Per descrivere un calcolo in modo preciso si usa la configurazione: una fotografia completa della macchina in un istante. Si scrive come stringa u q v, dove:
- u è il contenuto del nastro a sinistra della testina;
- q è lo stato corrente;
- v è il contenuto dalla posizione della testina in poi (il primo simbolo di v è quello letto), omettendo i blank finali.
Per esempio, 1 0 q₃ 1 1 significa: nastro 1011, stato q₃, testina sul terzo simbolo. Un calcolo è una sequenza di configurazioni in cui ciascuna segue dalla precedente applicando δ. Le configurazioni sono la chiave di molte dimostrazioni: permettono di codificare un intero calcolo come una stringa finita, e quindi di ragionare su calcoli con altre macchine.
Riconoscere e decidere
Il linguaggio riconosciuto da una macchina M è l'insieme delle stringhe che M accetta. Sulle altre M può rifiutare oppure non fermarsi.
Una macchina è un decisore se si ferma su ogni input. In quel caso diciamo che decide il linguaggio che riconosce.
Da qui due classi fondamentali:
- linguaggi Turing-riconoscibili (o ricorsivamente enumerabili): esiste una macchina che li riconosce;
- linguaggi decidibili (o ricorsivi): esiste un decisore.
Ogni linguaggio decidibile è riconoscibile, ma non vale il viceversa.
Un esempio svolto: {0ⁿ1ⁿ}
Costruiamo un decisore per {0ⁿ1ⁿ : n ≥ 0}, linguaggio che nessun automa finito riconosce. La strategia è cancellare uno 0 e un 1 alla volta.
- Se la cella corrente contiene il blank, accetta. Se contiene un 1, rifiuta. Se contiene uno 0, sostituiscilo con X.
- Spostati a destra saltando 0 e Y fino al primo 1. Se trovi un blank prima di un 1, rifiuta. Altrimenti sostituisci l'1 con Y.
- Torna a sinistra fino alla prima X e spostati di una cella a destra.
- Se leggi uno 0, ripeti dal passo 1 con quella cella. Se leggi una Y, scorri a destra saltando le Y: se trovi un blank accetta, se trovi un altro simbolo rifiuta.
Seguiamo l'input 0011:
- passo 1: X011;
- passo 2: X0Y1;
- ritorno e ripetizione: XXY1, poi XXYY;
- passo 4: dopo la seconda X la testina legge Y, scorre le Y e trova il blank. Accetta.
Con 0010 il secondo giro non trova un 1 dopo il secondo 0 marcato, perché incontra 0 e poi il blank: rifiuta. In ogni caso la macchina si ferma, quindi è un decisore. Il numero di passi è proporzionale a n², perché ogni giro attraversa il nastro.
Perché proprio questo modello
Il nastro, la testina e gli stati possono sembrare scelte arbitrarie. Il punto è che il modello è robusto: aggiungere più nastri, permettere il non determinismo o rendere il nastro infinito in entrambe le direzioni non cambia la classe dei linguaggi riconoscibili. E tutti gli altri modelli ragionevoli di calcolo noti calcolano esattamente le stesse funzioni. Questa robustezza giustifica l'uso della macchina di Turing come definizione di riferimento di «algoritmo».
In sintesi
- Una macchina di Turing ha stati finiti, un nastro illimitato e una testina che legge, scrive e si sposta.
- Gli esiti possibili sono tre: accetta, rifiuta oppure non si ferma.
- Le configurazioni descrivono un istante del calcolo con una stringa finita.
- Riconoscere non è decidere: un decisore deve fermarsi su ogni input.
- Il modello è robusto rispetto alle varianti, e per questo serve da definizione di algoritmo.
