Cos’è la macchina di Turing?

Alan Turing è definito da molti il padre dell’informatica. Forse però non sai il motivo di questa qualifica. Prima di tutto ti consiglio di guardarti il film “The imitation game” che sostanzialmente parla della sua vita e del suo contributo all’interno della seconda Guerra Mondiale. Se vuoi ne ho parlato nell’articolo sui migliori 30 documentari e film di informatica.

Tornando però a parlare delle cose importanti per questo articolo, devo dirti che il lavoro più famoso (e importante) di Alan Turing è On Computable Numbers del 1936, nel quale lui presentò la sua macchina di calcolo logico, chiamata in seguito Macchina di Turing.

La macchina di Turing non è un dispositivo fisico, come si potrebbe immaginare, ma un modello di macchina ideale.

L’enciclopedia Treccani definisce con le seguenti parole le caratteristiche e le capacità di una Macchina di Turing:

“Una macchina di Turing può essere interpretata fisicamente come l’interazione tra due ‘oggetti’: un dispositivo di controllo che può trovarsi in un numero finito di stati e una memoria esterna sequenziale, costituita da un nastro potenzialmente infinito diviso in celle in ciascuna delle quali è possibile leggere o scrivere un carattere dell’alfabeto della macchina. L’interazione è data da una testina di lettura/scrittura. In ogni istante, in base allo stato del controllo e al carattere letto, la macchina può:
a) cambiare o meno lo stato;
b) cambiare o meno il carattere sul nastro;
c) spostarsi o meno di una cella a sinistra o a destra.”

Probabilmente delle parole qui sopra citate non hai capito troppo, a meno che tu non sappia già qualcosa riguardo il funzionamento di una macchina di Turing. Tuttavia stai tranquillo, di seguito capirai di sicuro molto di più.

Sostanzialmente, la macchina di Turing ci permette di eseguire operazioni basilari, operando su un nastro idealmente infinito diviso in celle. Con operazioni basilari intendo: spostarsi di una cella, cancellare un carattere, sostituire un carattere. Sostanzialmente per dare le indicazioni ai simulatori della macchina di Turing è necessario spezzare qualsiasi operazione in passaggi più semplici, comprensibili all’automa.

Su internet esistono numerosi simulatori che permettono di testare molto facilmente le capacità di questo automa creato da Turing.  Ti consiglio di utilizzare quello presente al seguente link: MdT.

Ora ti troverai davanti ad una schermata come la seguente:

Puoi quindi vedere il nastro infinito di cui ti parlavo prima, inoltre è presente una testina, quella centrale, che punta sulla cella del nastro su cui puoi operare.

Prima di mostrarti un esempio molto semplice, devo dirti come si forniscono le istruzioni ad una macchina di Turing. Infatti le istruzioni sono da fornire attraverso delle quintuple. Per quintupla si intende un insieme di 5 elementi, contenuti tra due parentesi tonde e separati da delle virgole. Per esempio: (e1,e2,e3,e4,e5).

Devi sapere inoltre che il primo elemento della quintupla rappresenta lo stato iniziale, il secondo il carattere che il puntatore sta toccando, il terzo lo stato finale, il quarto il carattere che verrà sostituito a quello presente nella cella indicata e il quinto la direzione verso cui la testina si sposterà di un posto.

(s0, a, s1, b, >)

Per esempio in questa quintupla, sto dicendo alla macchina che quando si trova nello stato zero (s0) e trova una lettera ‘a’, deve passare allo stato uno (s1) e sovrascrivere alla ‘a’ una ‘b’. Ora la testina deve spostarsi di una cella a destra (>).

Ora per capire meglio come funziona prova a copiare le righe qui sotto nella colonna a destra del simulatore. Scrivi poi una serie di ‘a’ e ‘b’ nell’apposita barra sotto il pulsante Esegui (tipo: abababaaaa). Clicca quindi su Esegui. Dovresti notare che tutte le lettere si scambieranno, dove c’era una ‘a’ verrà scritta una ‘b’ e viceversa.

Esempio:

(0, a, 0, b, >)
(0, b, 0, a, >)
(0, -, fine, -, <)

Lo stato da cui si inizia sempre deve essere lo ‘0’ (zero).

Questo era un programmino davvero semplice, tuttavia puoi arrivare a fare cose che nemmeno ti immagini. Considera che esiste anche una gara nazionale di programmazione con la macchina di Turing! Se ti interessa dai un’occhiata qui: http://mdt.di.unipi.it/default.aspx.

Sono consapevole che in 1000 parole non sia possibile insegnare a programmare con la Macchina ti Turing, anche perchè non sarei capace di farlo nemmeno con un libro, tuttavia mi interessava presentarla, fornire una breve e semplice introduzione, dandoti poi alcuni riferimenti per approfondire il tema.

Infatti inserisco qui di seguito un elenco con i link che ti permetteranno di appassionarti a questo automa e di approfondire l’argomento:

Chi era Alan Turing

Storia della macchina di Turing

Indicazioni pratiche per programmare con il simulatore prima linkato

Qui di seguito invece ti inserisco una serie di esercizi per impratichirti, sono in ordine di difficoltà:

• Costruire una MdT che data una stringa scritta con un alfabeto di sole A e B mi faccia comparire una parola di sole A. (cioè le A restano A e le B diventano A)
• Costruire una MdT che data una stringa di A, B e C .Sostituisca ad ogni A la lettera C. ad ogni C la lettera A e le B restino B
• Costruire una MdT che data un numero scriva P se è pari e D se è dispari (es: Input 123 Output 123D)
• Costruire una MdT che dato un numero mi inverta le cifre 1 con 2 (cioè dove c’è scritto 1 scriverà 2 e dove c’è scritto 2 scriverà 1) e le altre cifre rimarranno invariate.
• Dato un numero in base dieci si scriva il numero sommato a 2.
• Dato un numero in base dieci si scriva il numero sommato a 3.
• Costruire una MdT che data una stringa di A e B mi scriva quante A sono presenti
• Macchina di Turing che esegua una moltiplicazione tra due numeri di massimo 3 cifre ciascuno (es. 234×123)
• Macchina di Turing che riconosce le stringhe palindrome (ossia uguali se lette da destra o sinistra)
• Macchina di Turing che converte i numeri decimali in notazione binaria

Ho deciso di inserirne solo 10, di cui gli ultimi sono abbastanza difficili, tuttavia per trovarne molti altri ti basterà cercare “esercizi macchina di turing” su Google.

L’articolo è terminato, spero di averti almeno interessato un po’.

Se hai dubbi, richieste o consigli, come al solito non esitare a commentare!