Le macchine di Turing

Le macchine di Turing (TM o Turing Machine) sono modelli computazionali fondamentali, equivalenti in potenza alla maggior parte dei dispositivi per scopi generali, capaci di definire le stesse funzioni calcolabili.

Esistono due tipologie di macchine di Turing a seconda di come gestiscono le transizioni tra gli stati.

• Macchina di Turing deterministica (DTM)
  Una DTM segue regole precise e univoche: per ogni stato e simbolo letto dalla testina, esiste una sola azione possibile che la macchina può eseguire, come muovere la testina, scrivere un simbolo o cambiare stato.
• Macchina di Turing non deterministica (NDTM)
  Una NDTM può avere multiple azioni possibili per ogni coppia stato-simbolo letto. Per ogni stato esistono più azioni possibili tra cui scegliere. In altre parole, da una data configurazione, la NDTM ha la capacità di "decidere" tra diverse transizioni possibili.

  Questo le conferisce una sorta di "potere di previsione" e le permette teoricamente di esplorare vari percorsi computazionali simultaneamente, il che può portare a una maggiore efficienza in termini di tempo di calcolo per certi tipi di problemi.

Le macchine di Turing deterministiche

Le macchine di turing deterministiche (DTM o Deterministic Turing Machine) rappresentano una specifica categoria di TM che operano secondo regole prestabilite.

Una DTM si compone di un'unità di controllo che gestisce transizioni tra stati e un nastro infinito diviso in celle, ciascuna delle quali può contenere un simbolo da un insieme limitato.

La testina di lettura/scrittura della macchina interagisce con il nastro leggendo e scrivendo simboli, e si sposta orizzontalmente seguendo le istruzioni del programma.

Le funzioni chiave di una DTM includono la lettura e la scrittura di simboli nella cella corrente, lo spostamento della testina e la modifica dello stato dell'unità di controllo basata sul simbolo letto e lo stato attuale.

Una TM è caratterizzata da un insieme finito di stati, uno stato iniziale, stati di accettazione che definiscono l'elaborazione riuscita di un input, simboli di input leggibili e un set più esteso di simboli scrivibili sul nastro, inclusi simboli speciali come il simbolo bianco per le celle vuote.

Questa struttura rende le TM e le DTM modelli universali nel campo della computazione.

Esempio

Facciamo un esempio con una Macchina di Turing (TM) che risolve un problema semplice: determinare se una stringa binaria contiene un numero pari di 1.

Considereremo un'implementazione deterministica di questa macchina.

La macchina lavora con un nastro infinito che inizia con la stringa binaria data e ha simboli bianchi (indicati come B) su tutti gli altri spazi.

Stati:

• q0: Stato iniziale.
• q1: Stato che indica un conteggio corrente dispari di 1.
• q_accept: Stato di accettazione, raggiunto quando la stringa è terminata e il conteggio dei 1 è pari.
• q_reject: Stato di rifiuto, raggiunto quando la stringa è terminata e il conteggio dei 1 è dispari.

Transizioni:

• Da q0 a q0: Se legge 0, scrive 0, muove a destra.
• Da q0 a q1: Se legge 1, scrive 1, muove a destra.
• Da q1 a q0: Se legge 1, scrive 1, muove a destra.
• Da q1 a q1: Se legge 0, scrive 0, muove a destra.
• Da q0 a q_accept: Se legge B (simbolo bianco che indica la fine della stringa), muove a destra.
• Da q1 a q_reject: Se legge B, muove a destra.

Adesso facciamo un esempio concreto, supponiamo di dover elaborare la stringa "1101" e analizziamo come si comporta la macchina:

1. Lo stato iniziale della macchina è q0.
2. Inizia in q0, legge 1 - Passa a q1, scrive 1, muove a destra.
3. In q1, legge 1 - Passa a q0, scrive 1, muove a destra.
4. In q0, legge 0 - Resta in q0, scrive 0, muove a destra.
5. In q0, legge 1 - Passa a q1, scrive 1, muove a destra.
6. In q1, legge B - Passa a q_reject, poiché il conteggio finale dei 1 è dispari.

Questo esempio mostra come una Macchina di Turing deterministica analizza una stringa e decide se il numero di 1 è pari o dispari, terminando in uno stato di accettazione o di rifiuto basato sul risultato del conteggio.

Possiamo rappresentare graficamente il funzionamento della Macchina di Turing, come quella descritta nell'esempio sopra, tramite un diagramma di stato che mostra gli stati della macchina e le transizioni tra questi stati.

Ecco una rappresentazione visuale:

I blocchi q0 e q1 sono gli stati della macchina usati per contare i numeri di 1 nella stringa: q0 tiene traccia di un conteggio pari di 1, mentre q1 tiene traccia di un conteggio dispari di 1.

Le frecce indicano le transizioni da uno stato all'altro. Ogni freccia è etichettata con il simbolo letto dalla testina della macchina e, nel contesto di un diagramma completo, includerebbe anche il simbolo da scrivere e la direzione in cui muovere la testina.

In questo esempio supponiamo che il simbolo scritto sia lo stesso di quello letto e che il movimento sia sempre a destra per semplicità.

Gli stati q_accept e q_reject sono gli stati finali che determinano rispettivamente l'accettazione e il rifiuto basati sulla parità del conteggio dei 1 al termine della stringa.

Questa rappresentazione grafica aiuta a visualizzare come la macchina di Turing processa una stringa di input e come il suo stato cambia in risposta ai simboli letti dal nastro.