In informatica, una macchina di Turing (o più brevemente MdT, in inglese TM, da Turing machine) è un modello matematico computazionale che descrive una macchina astratta: "In his 1936 paper, A. M. Turing defined the class of abstract machines that now bear his name. A Turing machine is a finite-state machine associated with a special kind of environment -- its tape -- in which it can store (and later recover) sequences of symbols".. che manipola (legge e scrive) i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite. A dispetto della sua apparente semplicità, questo modello è in grado di simulare la logica di qualunque algoritmo eseguibile su un computer reale.
Introdotta nel 1936 da Alan Turing come modello di calcolo per dare risposta all'Entscheidungsproblem (problema di decisione) proposto da Hilbert nel suo programma di fondazione formalista della matematica, è un potente strumento teorico che viene largamente usato nella teoria della calcolabilità e nello studio della complessità degli algoritmi, in quanto è di notevole aiuto agli studiosi nel comprendere i 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.
Descrizione La macchina di Turing ha la particolarità di essere retta da regole di natura molto semplice, ovvero di potersi descrivere come costituita da meccanismi elementari molto semplici; inoltre è possibile presentare a livello sintetico le sue evoluzioni mediante descrizioni meccaniche piuttosto intuitive. D'altra parte, essa ha la computabilità che si presume essere la massima: si dimostra, infatti, che è in grado di compiere tutte le elaborazioni effettuabili dagli altri modelli di calcolo noti all'uomo.
Tra questi modelli di calcolo 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 MdT in grado di risolverlo: questa è la cosiddetta congettura di Church-Turing, la quale 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 MdT si dicono "algoritmi Turing-computabili".
Caratteristiche Nel 1936 venne pubblicato un articolo di Alan Mathison Turing intitolato On computable numbers, with an application to the Entscheidungsproblem, in cui l'autore risolveva negativamente l'Entscheidungsproblem (o problema della decidibilità), lanciato nel 1900 da David Hilbert e Wilhelm Ackermann. La questione era stata posta da Hilbert nei seguenti termini: «esiste sempre, almeno in linea di principio, un metodo meccanico (cioè una maniera rigorosa) attraverso cui, dato un qualsiasi enunciato matematico, si possa stabilire se esso sia vero o falso?»
I vantaggi derivanti dal possedere un tale metodo sono enormi e meritano tutta l'enfasi che Hilbert e molti altri al suo seguito diedero alla questione: un tale algoritmo sarebbe in grado di risolvere tutti i problemi matematici e, molto di più, sarebbe possibile ridurre ogni ragionamento umano a mero calcolo meccanizzabile. Una prima forte risposta la diede il matematico boemo Gödel in occasione della seconda conferenza sull'epistemologia delle scienze esatte di Königsberg (1930), in cui espresse per la prima volta pubblicamente le idee racchiuse nel suo più celebre lavoro sull'incompletezza dei sistemi formali coerenti (primo teorema di incompletezza); Gödel dimostrò che la semplice coerenza di un sistema formale non può garantire che ciò che in esso viene dimostrato sia vero oppure falso. Il sogno di Hilbert stava già sfumando, quando Turing pubblicò il suo articolo, in cui dimostrò l'insolubilità dell'Entscheidungsproblem.
La soluzione proposta da Turing consiste nell'utilizzo di un modello matematico capace di simulare il processo di calcolo umano, scomponendolo nei suoi passi ultimi. La macchina è formata da una testina di lettura e scrittura con cui è in grado di leggere e scrivere su un nastro potenzialmente infinito, partizionato in maniera discreta in caselle. Ad ogni istante di tempo , la macchina si trova in uno stato interno ben determinato, risultato dell'elaborazione compiuta sui dati letti.
Lo stato interno, o configurazione, di un sistema è la condizione in cui si trovano le componenti della macchina ad un determinato istante di tempo . Le componenti da considerare sono: il numero della cella osservata il suo contenuto l'istruzione da eseguire Tra tutti i possibili stati, si distinguono: una configurazione iniziale, per (prima dell'esecuzione del programma) una configurazione finale, per (al termine dell'esecuzione del programma) delle configurazioni intermedie, per (prima dell'esecuzione dell'istruzione )
Implementare un algoritmo in questo contesto significa effettuare una delle cinque operazioni elementari spostarsi di una casella a destra spostarsi di una casella a sinistra scrivere un simbolo, preso da un insieme di simboli a sua disposizione, su una casella cancellare un simbolo già scritto sulla casella che si sta osservando fermarsi
Eseguire un'operazione , tra gli istanti di tempo e , vuol dire passare dallo stato interno al . Più formalmente, questo si esprime in simboli come: da leggersi come: nello stato interno la macchina osserva il simbolo a1, esegue l'operazione e si ritrova nello stato interno . Turing poté dimostrare che un tale strumento, dalle caratteristiche così rigidamente definite, è in grado di svolgere un qualsiasi calcolo, ma non si fermò qui; egli capì che la calcolabilità era in stretta relazione con la dimostrabilità, e, dunque, così come Gödel aveva distrutto i sogni di gloria dei Principia Mathematica di Russell e Whitehead, così la sua macchina poteva definitivamente chiudere la questione dell'Entscheidungsproblem.
Definizione Della MdT vengono considerate molteplici varianti (models) che si dimostrano avere la stessa potenza. Qui partiamo da una variante piuttosto semplice che possiamo chiamare macchina di Turing deterministica a un nastro, e con istruzioni a cinque campi. Altre varianti sono presentate più avanti.
Introduzione informale La 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; essa è 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 ad 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. La macchina è 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 MdT è 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 nel quale la macchina si trova, e dal carattere 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 vengono effettuate a ogni passo viene determinato dall'istruzione, che supponiamo unica, che ha come prime due componenti e ; le altre tre componenti dell'istruzione forniscono nell'ordine il nuovo stato, il nuovo carattere, e una richiesta di spostamento verso sinistra, nullo, o verso destra.
Un'evoluzione della macchina consiste in una sequenza di possibili "configurazioni", ognuna di queste costituita dallo stato interno attuale, dal contenuto del nastro (una stringa di lunghezza finita), e dalla posizione sul nastro della testina di I/O. Nei casi più semplici l'evoluzione ad un certo punto si arresta, in quanto non si trova nessuna istruzione in grado di farla proseguire. Si può avere un arresto in una configurazione "utile", dal punto di vista del problema che si vuole risolvere; in tal caso quello che si trova registrato sul nastro all'atto dell'arresto, rappresenta il risultato dell'elaborazione. Si può avere però anche un arresto "inutile", che va considerato come una conclusione erronea dell'elaborazione. Va subito detto che può anche accadere che un'evoluzione non abbia mai fine (Vedi la successiva sezione e Problema della fermata).
Impostazione formale Si definisce macchina di Turing deterministica a un nastro e istruzioni a cinque campi, termine che abbreviamo con MdT1n5i, una macchina formale della seguente forma:
è un insieme finito detto insieme degli stati della macchina;
è un elemento di detto stato iniziale della ;
è un sottoinsieme di detto insieme degli stati finali della ;
è un alfabeto finito detto alfabeto del nastro della
è un carattere dell'alfabeto detto segno di casella vuota del nastro della
è detta funzione di transizione della macchina.
Se , la corrispondente quintupla può considerarsi come l'istruzione che viene eseguita quando la macchina si trova nello stato e la testina di I/O legge sulla casella sulla quale è posizionata; essa comporta la transizione allo stato , la scrittura del carattere e: quando lo spostamento della testina di una posizione a sinistra, quando nessuno spostamento della testina, quando lo spostamento della testina di una posizione a destra.
Ampiezza della portata e congettura di Church-Turing
L'importanza della MdT deriva dal fatto che permette di compiere tutte le elaborazioni effettuate mediante le macchine (elettroniche o meccaniche) apparse nella storia dell'umanità, incluse le elaborazioni che oggi si eseguono con le tecnologie più avanzate e gli odierni computer, e perfino le dimostrazioni matematiche che l'umanità ha raccolto nel corso della sua storia.
Infatti, tutte le macchine che si conoscono possono essere ricondotte al modello estremamente semplice di Turing. Ad esempio, anche i più complessi computer odierni possono essere ricondotti a questo modello: Innanzitutto, si individuano macchine relativamente semplici che effettuino le operazioni aritmetiche di base, e schemi di composizione di queste macchine che permettono di calcolare tutte le funzioni che hanno in ingresso numeri naturali. Queste funzioni corrispondono alle espressioni ottenute combinando come si vuole le suddette operazioni. Quindi, si individuano versioni della MdT più ricche di risorse, che consentano di descrivere più agevolmente operazioni via via più complesse e che riguardino entità discrete dei generi più vari (numeri razionali, grafi, stringhe, espressioni simboliche di varia natura, ...), ma tutte riconducibili a numeri naturali; le elaborazioni e le entità dei tipi più vari devono essere prese in considerazione per sostenere la congettura di Church-Turing.