Macchina di Turing
Perché una macchina di Turing ha un nastro
Nella lezione precedente abbiamo visto che un Automa a Stati Finiti (DFA) ha un numero fissato e finito di stati . Questo significa che la sua memoria è limitata a priori: se un automa ha stati, non può “contare” oltre .
Cosa succede allora se chiediamo a un DFA di riconoscere il semplice linguaggio (tante seguite dallo stesso numero di , oppure espressioni con un numero arbitrario di parentesi aperte e chiuse)? Nessun Automa a Stati Finiti può farlo! Infatti, poiché può essere grande a piacere (es. un miliardo di ), per contare tutte le prima di confrontarle con le l’automa esaurirebbe i suoi stati finiti e per il principio dei cassetti (Pigeonhole Principle) entrerebbe in un ciclo, confondendo due valori diversi di .
Nel 1936 il giovane matematico inglese Alan Turing, cercando di dare una definizione matematica rigorosa di cosa significhi “calcolare tramite un algoritmo”, ideò una macchina astratta dotata di una memoria esterna illimitata su cui poter sia leggere sia scrivere: la Macchina di Turing (MdT). Con memoria estendibile, il modello descrive le funzioni calcolabili in modo effettivo. Un calcolatore fisico è soggetto a limiti di memoria e tempo.
Struttura astratta e Definizione Formale della Macchina di Turing
Le 3 componenti fisiche astratte
Immaginiamo la Macchina di Turing come composta da:
- Un Nastro (Tape) potenzialmente infinito in entrambe le direzioni, diviso in celle consecutive. Ciascuna cella contiene un singolo simbolo. Inizialmente sul nastro è scritta la stringa di input , mentre tutte le infinite celle rimanenti a sinistra e a destra contengono un simbolo speciale di “cella vuota” chiamato Blank ( oppure o ).
- Una Testina di Lettura/Scrittura (Read/Write Head) posizionata su una cella del nastro. Ad ogni passo la testina può leggere il simbolo sotto di sé, sovrascriverlo con un nuovo simbolo e spostarsi di una cella a sinistra (), a destra () oppure rimanere ferma (, Stay).
- Un’Unità di Controllo a Stati Finiti dotata di un registro di stato che memorizza lo stato corrente .
flowchart TD subgraph Nastro["Nastro Illimitato (diviso in celle)"] direction LR B1["..."] --- B2["B (Blank)"] --- C1["0"] --- C2["1"] --- C3["1"] --- C4["0"] --- B3["B (Blank)"] --- B4["..."] end HEAD["Testina di Lettura / Scrittura\n(legge, scrive e si muove L / R / S)"] ==> C2 CTRL["Unità di Controllo\nStato Corrente: q_i\nTabella delle Quintuple δ"] <==> HEAD
Definizione Formale (Sestupla / Settupla e Quintuple di transizione)
Una Macchina di Turing Deterministica è definita formalmente dalla tupla:
dove:
-
: insieme finito e non vuoto degli stati interni.
-
: alfabeto di input (, con ).
-
(Gamma): alfabeto del nastro (insieme finito dei simboli che possono essere scritti sul nastro; include l’alfabeto di input , il simbolo Blank ed eventuali simboli ausiliari di lavoro come ).
-
: stato iniziale (all’avvio la testina è posizionata sul primo simbolo a sinistra della stringa di input).
-
: il simbolo Blank (cella vuota).
-
: insieme degli stati finali (o di arresto/accettazione).
-
: funzione di transizione (parziale):
Ogni istruzione della funzione può essere scritta come una quintupla:
che significa: “Se la macchina si trova nello stato e la testina legge sul nastro il simbolo , allora passa nello stato , scrive nella cella corrente il simbolo e sposta la testina nella direzione ()”.
Computazione, Terminazione, Tesi di Church-Turing e Halting Problem
Configurazione istantanea e Computazione
In ogni istante, la fotografia completa della Macchina di Turing (detta configurazione istantanea) è determinata da tre elementi:
- Il contenuto attuale della porzione non vuota del nastro.
- Lo stato corrente .
- La posizione esatta della testina sul nastro.
Data una stringa di input , una computazione della MdT può avere tre esiti possibili:
- Terminazione con Accettazione (o Calcolo completato): la macchina raggiunge uno stato finale per il quale non sono definite ulteriori mosse e si arresta (Halt). Se la MdT è usata come trasduttore (calcolatore di funzioni), la stringa rimasta scritta sul nastro al momento dell’arresto è l’output del calcolo!
- Terminazione con Rifiuto: la macchina si blocca in uno stato non finale perché per la coppia non esiste alcuna quintupla nella tabella .
- Ciclo infinito (Non terminazione): la macchina continua a muoversi all’infinito senza mai fermarsi (ad esempio spostandosi sempre a destra sulle celle Blank: ).
La Tesi di Church-Turing
Negli anni ‘30 diversi matematici proposero modelli formali di calcolo apparentemente molto diversi tra loro (la Macchina di Turing, il -calcolo di Alonzo Church, le funzioni ricorsive di Gödel e Kleene). Si dimostrò che tutti questi modelli calcolano esattamente la stessa classe di funzioni! Da qui nasce il principio fondante dell’informatica:
Tesi di Church-Turing: Qualsiasi funzione o problema che sia “intuitivamente calcolabile” tramite un algoritmo effettivo (eseguibile da un qualsiasi computer fisico o linguaggio di programmazione come il C) è calcolabile da una Macchina di Turing.
Macchina di Turing Universale (UTM) e Problema della Fermata (Halting Problem)
- Macchina di Turing Universale (): Turing dimostrò che è possibile codificare la tabella delle quintuple di una qualunque MdT come una stringa di simboli e fornirla sul nastro insieme ai dati a una speciale MdT “interprete” , capace di simulare passo dopo passo il comportamento di su . La Macchina Universale di Turing è il modello teorico del moderno computer programmabile (architettura di von Neumann), in cui programmi e dati risiedono nella stessa memoria!
- Il Problema della Fermata (Halting Problem): Esiste un problema che nessun algoritmo e nessun computer potrà mai risolvere? Sì! Turing dimostrò per assurdo (con un argomento diagonale) che è indecidibile stabilire in generale, data una qualsiasi Macchina di Turing (o programma C) e un qualsiasi input , se terminerà la sua esecuzione su oppure proseguirà indefinitamente. Non può esistere un controllo universale automatico che individui tutti i loop infiniti!
Macchina universale e programma memorizzato
Indichiamo con una codifica finita della tabella delle transizioni di una macchina . Una macchina universale legge una coppia codificata , distingue la descrizione dalle celle che rappresentano l’input e simula un passo di alla volta. La simulazione conserva arresto e risultato. Se prosegue indefinitamente su , anche la simulazione prosegue. La codifica tratta come dati sia la descrizione della macchina sia il suo input.
L’architettura a programma memorizzato usa una memoria che contiene anche le istruzioni. La CPU legge l’istruzione indicata dal contatore di programma, la interpreta, accede ai dati necessari e aggiorna lo stato. Il nastro ricorda il ruolo della memoria e il controllo finito ricorda parte del ruolo della CPU. La testina percorre celle adiacenti, mentre una RAM è indirizzabile direttamente. Il nastro del modello è estendibile, mentre una macchina fisica dispone di risorse finite. L’analogia aiuta a seguire il flusso di istruzioni e dati nel modello RAM.
Esempi guidati
Esempio 1: Complemento bit a bit di una stringa binaria (Trasduttore)
Problema: Costruire una Macchina di Turing che, data sul nastro una stringa binaria (con la testina inizialmente sul primo bit a sinistra), inverta tutti i bit ( e ) e riporti la testina sul primo bit a sinistra prima di fermarsi nello stato finale .
Strategia dell’algoritmo:
- Nello stato iniziale , scorriamo la stringa verso destra (): se leggiamo
0scriviamo1e andiamo a destra; se leggiamo1scriviamo0e andiamo a destra. - Quando leggiamo il primo Blank
$B$a destra della stringa, abbiamo invertito tutti i bit! Lasciamo$B$, passiamo nello stato di riavvolgimento e ci spostiamo di una cella a sinistra (). - Nello stato , scorriamo a ritroso verso sinistra () lasciando inalterati gli
0e gli1finché incontriamo il Blank$B$che precede l’inizio della stringa. - Appena leggiamo
$B$a sinistra, facciamo un passo a destra () per posizionarci esattamente sul primo bit della stringa ed entriamo nello stato finale .
stateDiagram-v2 direction LR [*] --> q0 q0 --> q0 : 0 / 1, R\n1 / 0, R q0 --> q1 : B / B, L q1 --> q1 : 0 / 0, L\n1 / 1, L q1 --> qf : B / B, R qf --> [*]
Tabella completa delle Quintuple :
| Stato corrente | Simbolo letto | Nuovo stato | Simbolo scritto | Movimento | Commento operativo |
|---|---|---|---|---|---|
0 | 1 | Inverte 0 in 1 e avanza a destra | |||
1 | 0 | Inverte 1 in 0 e avanza a destra | |||
| Fine stringa raggiunta: inizia a tornare a sinistra | |||||
0 | 0 | Scorre a sinistra senza modificare | |||
1 | 1 | Scorre a sinistra senza modificare | |||
| Raggiunto il Blank di sinistra: si posiziona sul bit e termina |
Esempio 2: Incremento di di un numero binario
Problema: Dato sul nastro un numero binario intero senza segno (es. 1011, cioè ), sommare ottenendo sul nastro 1100 ().
Strategia dell’algoritmo (come l’addizione in colonna!):
- Stato (Vai in fondo a destra sul bit meno significativo): scorre tutti gli
0e1verso destra () finché trova$B$; a quel punto fa un passo a sinistra () entrando in (stato di “riporto da sommare”). - Stato (Somma il riporto di 1 risalendo verso sinistra):
- Se legge
0: sommando diventa1senza ulteriore riporto! Scrive1e passa direttamente allo stato finale (). - Se legge
1: con riporto di 1! Scrive0, resta in e si sposta a sinistra () per propagare il riporto al bit successivo. - Se legge
$B$(caso in cui il numero era composto da soli1, es.111+ 1 =1000): scrive1nella cella Blank di sinistra e termina in ().
- Se legge
Quintuple:
- , ,
- (propaga il riporto a sinistra)
- (assorbe il riporto e termina)
- (aggiunge una cifra in testa se tutti i bit erano
1e termina)
Esempio 3: Riconoscimento del linguaggio non regolare
Ecco perché la Macchina di Turing supera i limiti degli Automi a Stati Finiti! Per verificare che il numero di sia uguale al numero di (es. aaabbb), la MdT usa il nastro come blocco degli appunti procedendo a “zig-zag”:
- Stato : legge la prima disponibile a sinistra, la “cancellla/marca” sovrascrivendola con e passa a muovendosi a destra ().
- Stato : salta tutte le restanti e le già marcate muovendosi a destra () finché trova la prima libera; la marca sovrascrivendola con e passa a tornando a sinistra ().
- Stato : torna indietro a sinistra () saltando e finché incontra l’ultima marcata; fa un passo a destra () e torna in per ripetere il ciclo sulla coppia successiva .
- Quando in , subito a destra dell’ultima , non ci sono più ma si incontra direttamente , passa a per verificare che tutte le restanti celle fino a siano solo (nessuna in eccesso): se trova , accetta in !
Traccia del nastro per aabb:
Errori frequenti
Errori da evitare
- Dimenticare che la testina legge un solo simbolo alla volta e non “vede” le celle adiacenti
Una MdT non può testare condizioni come “se la cella successiva è Blank allora fermati”: deve prima spostarsi a destra fino a leggere effettivamente il simbolo Blank$B$, e poi fare un passo indietro a sinistra () per tornare sull’ultimo carattere della stringa.- Sovrascrivere il simbolo letto per distrazione quando si vuole solo scorrere il nastro
Se nello stato vogliamo solo spostarci a destra sopra gli0e gli1senza alterarli, dobbiamo scrivere due quintuple distinte: (se legge0riscrive0) e (se legge1riscrive1).- Creare loop infiniti dimenticando la condizione di arresto sul Blank
$B$
Se una regola dice , una volta finita la stringa la testina correrà verso destra sul nastro infinito per sempre!
Esercizi di prova
Esercizio 1. Simulazione manuale di una Macchina di Turing (Base)
Data la Macchina di Turing con stato iniziale , stato finale e le seguenti quintuple:
Mostra passo dopo passo il contenuto del nastro e lo stato della macchina partendo dall’input . Qual è la funzione generale calcolata da questa macchina?
Soluzione
Indichiamo con la sottolineatura la posizione della testina:
- : legge in scrive , passa in , va a destra ().
- : legge in lascia , resta in , va a destra ().
- : legge in lascia , torna in , va a destra ().
- : legge in scrive , passa in , va a destra ().
- : legge in lascia , passa in e si arresta ().
Output sul nastro:
bbab.
Funzione generale: La macchina sostituisce con una sì e una no (cioè trasforma in tutte le occorrenze di di posizione dispari: la , la , la , ecc.).
Esercizio 2. Addizione in notazione unaria (Base)
In notazione unaria un numero naturale è rappresentato da una sequenza di bastoncini 1 (es. , ). Supponiamo che sul nastro siano scritti due numeri unari separati dal simbolo +, ad esempio 111+11 ().
Scrivi la tabella delle quintuple di una MdT che calcoli la loro somma producendo sul nastro una singola sequenza contigua di 1 (nell’esempio: 11111, cioè ).
Soluzione
Idea furba: In unario, per unire una sequenza di uno e una di uno separate da
+in un’unica sequenza di uno, basta trasformare il+in1e poi cancellare (sostituire con Blank$B$) l’ultimo1in fondo a destra!
111+1111111111111B.Quintuple:
- (scorre il primo numero)
- (trovato il
+, lo trasforma in1e passa a )- (scorre il secondo numero fino alla fine)
- (raggiunto il Blank finale, torna indietro di 1 cella sull’ultimo
1)- (cancella l’ultimo
1scrivendo$B$e si ferma in !)
Esercizio 3. Cancellazione dell’ultimo carattere o aggiunta in coda (Intermedio)
Scrivi le quintuple di una Macchina di Turing su che, data una stringa non vuota sul nastro:
- Se inizia con , aggiunge una in fondo a destra della stringa.
- Se inizia con , aggiunge una in fondo a destra della stringa.
Soluzione
Basta leggere il primo carattere in e “ricordarlo” ramificando in due stati diversi ( se iniziava con , se iniziava con ), che scorrono la stringa fino al primo Blank
$B$a destra e vi scrivono il carattere memorizzato:
- Da (lettura del primo carattere):
- Nello stato (scorre fino al Blank e scrive ):
- , ,
- Nello stato (scorre fino al Blank e scrive ):
- , ,
Esercizio 4. Verifica di stringa palindroma con Macchina di Turing (Avanzato)
Descrivi gli stati e scrivi le quintuple di una Macchina di Turing che riconosca il linguaggio delle stringhe palindrome su (cancellando progressivamente con $B$ il primo e l’ultimo carattere e verificando che coincidano).
Soluzione
Strategia:
- In leggiamo il primo carattere a sinistra:
- Se è
$B$, la stringa è stata completamente svuotata con successo accettiamo in !- Se è , lo cancelliamo scrivendo
$B$e andiamo a destra nello stato fino in fondo alla stringa.- Se è , lo cancelliamo scrivendo
$B$e andiamo a destra nello stato fino in fondo alla stringa.- Arrivati al Blank di destra in (o ), torniamo a sinistra di una cella nello stato (o ):
- Se troviamo
$B$(la stringa aveva un solo carattere centrale rimasto!), accettiamo in .- Se troviamo il carattere corrispondente ( per , per ), lo cancelliamo con
$B$e torniamo a sinistra con lo stato fino al Blank di sinistra, per poi ripartire da !- Se troviamo il carattere opposto, non c’è transizione e la macchina rifiuta.
Quintuple complete:
- ,
- , ,
- , ,
- ,
- ,
- , ,
Esercizio 5. Confronto teorico tra FSA e Macchina di Turing (Avanzato)
Spiega sinteticamente le tre differenze strutturali fondamentali tra un Automa a Stati Finiti (DFA) e una Macchina di Turing (MdT), indicando perché queste differenze permettono alla MdT di riconoscere linguaggi di Tipo 0, 1 e 2 che un DFA non può riconoscere.
Soluzione
Le tre differenze strutturali sono:
- Capacità di Scrittura sul nastro: un DFA ha una testina di sola lettura, mentre la MdT può scrivere e modificare i simboli sul nastro usando un alfabeto ausiliario .
- Movimento Bidirezionale della testina: un DFA legge la stringa in una sola passata rigorosamente da sinistra verso destra; la MdT può muovere la testina sia a destra () sia a sinistra () (o restare ferma ), ripassando più volte sulle stesse celle.
- Memoria Illimitata: il nastro della MdT è potenzialmente infinito (dotato di infinite celle Blank ). Mentre un DFA può ricordare solo un’informazione finita codificata nei suoi stati, la MdT può usare il nastro come memoria di lavoro illimitata per contare, marcare simboli (come in o ) e calcolare qualsiasi funzione algoritmicamente computabile.
Provenienza del materiale
- Slide e dispensa ufficiale del corso:
C1PROG1U1L2_Macchina_di_Turing.pdf(Unità 1, Lezione 2 — La Macchina di Turing, quintuple, calcolabilità e tesi di Church-Turing). - Marco Anisetti, Fondamenti,
Appunti_di_fine_Unita_1.pdf, cap. 4. - Guida unica di studio – Fondamenti,
Guida_Unita_1_teoria_approfondimenti_per_argomento.pdf, §§ 10–11. - Appunti Avanzati di Programmazione e Algoritmi I,
AppuntiInformatica-v3.pdf, § 4.