La Macchina di Turing

Una macchina di Turing è una macchina ideale che manipola i dati contenuti in un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. In altri termini, si tratta di un modello astratto che definisce una macchina in grado di eseguire algoritmi e dotata di un nastro potenzialmente infinito in cui può leggere e/o scrivere dei simboli.

La macchina di Turing è un potente strumento teorico che viene largamente utilizzato nella teoria della calcolabilità e nello studio della complessità degli algoritmi, in quanto è di notevole aiuto agli studiosi per la comprensione dei limiti del calcolo meccanico. La sua importanza è tale che, oggi, per definire in modo formalmente preciso la nozione di algoritmo, si tende a ricondurlo alle elaborazioni effettuabili con macchine di Turing.

Come modello di calcolo, la macchina di Turing è stata introdotta nel 1936 da Alan Turing per dare risposta all’Entscheidungproblem (problema di decisione) proposto da Hilbert nel suo programma di fondazione formalista della matematica.

La macchina di Turing presenta la particolarità di essere retta da regole di natura molto semplice; può essere descritta come costituita da meccanismi elementari molto semplice. Inoltre, è possibile presentare a livello sintetico le sue evoluzioni mediante descrizioni meccaniche piuttosto intuitive. D’altra parte, la macchina di Turing ha la portata computazionale (potere computazionale) che si presume essere la massima: si dimostra, infatti, che essa è in grado di effettuare tutte le elaborazioni effettuabili dagli altri modelli di calcolo noti all’uomo. Tra questi ricordiamo le funzioni ricorsive di Jacques Herbrand e Kurt Gödel, il lambda calcolo di Alonzo Church e Stephen Kleene, la logica combinatoria di Moses Schönfinkel e Haskell Curry, gli algoritmi di Markov, i sistemi di Thue, i sistemi di Post, le macchine di Hao Wang e le macchine a registri elementari o RAM astratte di Marvin Minsky. Di conseguenza, si è consolidata la convinzione che per ogni problema calcolabile esista una macchina di Turing in grado di risolverlo: questa è la cosiddetta congettura di Church-Turing che postula in sostanza che per ogni funzione calcolabile esista una macchina di Turing equivalente, ossia che l’insieme delle funzioni calcolabili coincida con quello delle funzioni ricorsive.

Gli algoritmi che possono essere implementati da una macchina di Turing si dicono “algoritmi Turing-computabili”

Qualche nota introduttiva

Della macchina di Turing vengono considerate molteplici varianti (models) che si dimostrano avere la stessa portata. Per il momento prendiamo in considerazione una variante piuttosto semplice, che possiamo chiamare macchina di Turing deterministica a un nastro e con istruzioni a cinque campi.

Questa macchina può agire sopra un nastro che si presenta come una sequenza di caselle nelle quali possono essere registrati simboli di un ben determinato alfabeto finito. La macchina è dotata di una testina di lettura e scrittura (I/O) con cui è in grado di effettuare operazioni di lettura e scrittura su una casella del nastro. La macchina si evolve nel tempo e in ogni istante si può trovare in uno stato interno ben determinato facente parte di un insieme finito di stati. Inizialmente sul nastro viene posta una stringa che rappresenta i dati che caratterizzano il problema che viene sottoposto alla macchina. Questa è dotata anche di un repertorio finito di istruzioni che determinano la sua evoluzione in conseguenza dei dati iniziali. L’evoluzione si sviluppa per passi successivi che corrispondono a una sequenza discreta di istanti successivi. Le proprietà precedenti sono comuni a molte macchine formali (automa a stati finiti, automa a pila…). Caratteristica delle macchine di Turing è quella di disporre di un nastro potenzialmente infinito, cioè estendibile quanto si vuole qualora questo si renda necessario.

Ogni passo dell’evoluzione viene determinato dallo stato attuale s nel quale la macchina si trova e dal carattere c che la testina di I/O trova sulla casella del nastro su cui è posizionata e si concretizza nell’eventuale modifica del contenuto della casella, nell’eventuale spostamento della testina di una posizione verso destra o verso sinistra e nell’eventuale cambiamento dello stato. Quali azioni vengano effettuate ad ogni passo viene determinato dalla istruzione, che supponiamo unica, che ha come prime due componenti sc; le altre componenti della istruzione forniscono nell’ordine il nuovo stato, il nuovo carattere e una richiesta di spostamento verso sinistra, nullo o verso destra.

Una evoluzione della macchina consiste in una sequenza di sue possibili “configurazioni”, essendo ogni configurazione costituita dallo stato interno attuale, dal contenuto del nastro (una stringa di lunghezza finita) e dalla posizione sul nastro della testina di I/O.