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:

  1. 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 ).
  2. 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).
  3. 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:

  1. : insieme finito e non vuoto degli stati interni.

  2. : alfabeto di input (, con ).

  3. (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 ).

  4. : stato iniziale (all’avvio la testina è posizionata sul primo simbolo a sinistra della stringa di input).

  5. : il simbolo Blank (cella vuota).

  6. : insieme degli stati finali (o di arresto/accettazione).

  7. : 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:

  1. Il contenuto attuale della porzione non vuota del nastro.
  2. Lo stato corrente .
  3. La posizione esatta della testina sul nastro.

Data una stringa di input , una computazione della MdT può avere tre esiti possibili:

  1. 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!
  2. Terminazione con Rifiuto: la macchina si blocca in uno stato non finale perché per la coppia non esiste alcuna quintupla nella tabella .
  3. 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:

  1. Nello stato iniziale , scorriamo la stringa verso destra (): se leggiamo 0 scriviamo 1 e andiamo a destra; se leggiamo 1 scriviamo 0 e andiamo a destra.
  2. 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 ().
  3. Nello stato , scorriamo a ritroso verso sinistra () lasciando inalterati gli 0 e gli 1 finché incontriamo il Blank $B$ che precede l’inizio della stringa.
  4. 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 correnteSimbolo lettoNuovo statoSimbolo scrittoMovimentoCommento operativo
01Inverte 0 in 1 e avanza a destra
10Inverte 1 in 0 e avanza a destra
Fine stringa raggiunta: inizia a tornare a sinistra
00Scorre a sinistra senza modificare
11Scorre 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!):

  1. Stato (Vai in fondo a destra sul bit meno significativo): scorre tutti gli 0 e 1 verso destra () finché trova $B$; a quel punto fa un passo a sinistra () entrando in (stato di “riporto da sommare”).
  2. Stato (Somma il riporto di 1 risalendo verso sinistra):
    • Se legge 0: sommando diventa 1 senza ulteriore riporto! Scrive 1 e passa direttamente allo stato finale ().
    • Se legge 1: con riporto di 1! Scrive 0, 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 soli 1, es. 111 + 1 = 1000): scrive 1 nella cella Blank di sinistra e termina in ().

Quintuple:

  • , ,
  • (propaga il riporto a sinistra)
  • (assorbe il riporto e termina)
  • (aggiunge una cifra in testa se tutti i bit erano 1 e 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”:

  1. Stato : legge la prima disponibile a sinistra, la “cancellla/marca” sovrascrivendola con e passa a muovendosi a destra ().
  2. 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 ().
  3. 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 .
  4. 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

  1. 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.
  2. Sovrascrivere il simbolo letto per distrazione quando si vuole solo scorrere il nastro
    Se nello stato vogliamo solo spostarci a destra sopra gli 0 e gli 1 senza alterarli, dobbiamo scrivere due quintuple distinte: (se legge 0 riscrive 0) e (se legge 1 riscrive 1).
  3. 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?

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è ).

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.

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

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.


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.