Macchina di Turing

Un esempio di macchina di Turing

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 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 essa sia in grado di effettuare 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 $t_{1}$, la macchina si trova in uno stato interno $s_{1}$ 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 $t$. 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 $t=t_{0}$ (prima dell'esecuzione del programma)
• una configurazione finale, per $t=t_{n}$ (al termine dell'esecuzione del programma)
• delle configurazioni intermedie, per $t=t_{i}$ (prima dell'esecuzione dell'istruzione $o_{i}$)

Implementare un algoritmo in questo contesto significa effettuare una delle quattro 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 sta osservando
• fermarsi

Eseguire un'operazione $o_{1}$, tra gli istanti di tempo $t_{1}$ e $t_{2}$, vuol dire passare dallo stato interno $s_{1}$ al $s_{2}$. Più formalmente, questo si esprime in simboli come: $\{s_{1},a_{1},o_{1},s_{2}\}$ da leggersi come: nello stato interno $s_{1}$ la macchina osserva il simbolo a₁, esegue l'operazione $o_{1}$ e si ritrova nello stato interno $s_{2}$. 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ì le sue macchine potevano definitivamente chiudere la questione dell'Entscheidungsproblem.

Definizione

Della MdT vengono considerate molteplici varianti (models) che si dimostrano avere la stessa portata. 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 $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 vengono effettuate a ogni passo viene determinato dall'istruzione, che supponiamo unica, che ha come prime due componenti $s$ e $c$; 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 sue possibili "configurazioni", ogni configurazione essendo 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:

$T=\langle S,s_{0},F,A,\beta ,\delta \rangle \quad {\mbox{dove}}$

$S$ è un insieme finito detto insieme degli stati della macchina;

$s_{0}$ è un elemento di $S$ detto stato iniziale della $T$;

$F$ è un sottoinsieme di $S$ detto insieme degli stati finali della $T$;

$A$ è un alfabeto finito detto alfabeto del nastro della $T$

$\beta$ è un carattere dell'alfabeto $A$ detto segno di casella vuota del nastro della $T$

$\delta ~:~S\times A\to S\times A\times \{-1,0,+1\}$ è detta funzione di transizione della macchina.

Se $\delta (s,a)=\langle t,b,m\rangle$, la corrispondente quintupla $\langle s,a,t,b,m\rangle$ può considerarsi come l'istruzione che viene eseguita quando la macchina si trova nello stato $s$ e la testina di I/O legge $a$ sulla casella sulla quale è posizionata; essa comporta la transizione allo stato $t$, la scrittura del carattere $b$ e:

• quando $m=-1$ lo spostamento della testina di una posizione a sinistra,
• quando $m=0$ nessuno spostamento della testina,
• quando $m=+1$ 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.
• Proseguendo in questa direzione, si introducono MdT dotate di memorie complesse, come sequenze di nastri e memorie bidimensionali e tridimensionali, assimilabili ai dischi e alle pile di dischi; macchine che sono dotate della capacità di organizzare le istruzioni in un modo assimilabile al richiamo di un sottoprogramma come richiesto dai linguaggi di programmazione in uso.
• Ulteriori arricchimenti possono includere calcoli simbolici ed elaborazioni parallele.
• A questo punto si deve anche aggiungere che della MdT risulta opportuno anche considerare varianti non deterministiche, macchine formali che sono in grado di portare avanti contemporaneamente diverse elaborazioni, in numero illimitato. Queste macchine formali, a prima vista lontane da modelli di meccanismi concretamente realizzabili, possono considerarsi idealizzazioni di sistemi di computer che operano in parallelo, sistemi che la odierna tecnologia consente di realizzare abbastanza comunemente (i cosiddetti cluster).

Con questo ragionamento si ottengono macchine formali che, in linea di principio, si possono ricondurre alla MdT introdotta inizialmente, ma che possono essere programmate molto più agevolmente, e soprattutto che possono essere realizzate con le tecnologie disponibili oggi. Dimostrare che una di queste macchine può risolvere un certo problema vuol dire dimostrare che anche la MdT può risolverlo. La conclusione è che tutte le computazioni effettuabili dalle macchine a noi note sono effettuabili anche dalla MdT.

Una macchina che permetta di risolvere tutti i problemi risolvibili anche dalla MdT si dice "Turing-equivalente". La conclusione è che tutte le computazioni effettuabili dalla MdT sono effettuabili anche da tutte le macchine di cui si è in grado di dimostrare l'equivalenza con la MdT.

Quindi, l'importanza della MdT è duplice: non solo è il modello teorico di macchina più "potente" che si conosca, ma può essere usato anche per verificare la potenza di nuovi modelli teorici. È possibile dimostrare l'equivalenza con la MdT anche servendosi di un modello più semplice e che si sa già essere Turing-equivalente. Ciò permette di riutilizzare facilmente, per un certo modello di macchina, i risultati teorici ottenuti per altri modelli di macchina.
Inoltre, la MdT e gli altri modelli possono essere usati per dimostrare le capacità computazionali dei linguaggi di programmazione (in quanto vengono dimostrate le capacità delle rispettive macchine astratte).

Tutte queste considerazioni rendono ragionevole sostenere la congettura di Church-Turing. Tuttavia, esse riguardano la calcolabilità degli algoritmi, e non la loro trattabilità: macchine equivalenti sono realizzate in modo diverso, e quindi possono eseguire la stessa computazione con un diverso numero di passi o dispendio di risorse (memoria, tempo, e altre). Ad esempio, un calcolo che un odierno computer esegue in pochi secondi richiederebbe un numero enorme di passi se eseguito su un meccanismo dotato di dispositivi operativi estremamente semplici come quelli della MdT. In sintesi, macchine diverse possono risolvere gli stessi problemi con programmi che hanno una diversa complessità computazionale.

Il problema dell'arresto e la sua indecidibilità

In talune circostanze può essere utile considerare una MdT che presenta un'evoluzione illimitata (infatti si considerano infinite le risorse di spazio e tempo a disposizione della macchina). Ad esempio interessa far procedere "illimitatamente" (cioè "quanto risulta utile") una MdT che genera gli elementi di una successione di oggetti (ad es. i successivi numeri primi, o i successivi numeri di Mersenne, o le successive cifre decimali di un numero irrazionale come pi greco). In altri casi invece un'evoluzione illimitata di una MdT è considerata un insuccesso. Quando si vuole che una MdT ricerchi in un insieme numerabile un elemento con determinate caratteristiche ed essa procede nella ricerca senza fornire alcuna indicazione, ci si trova in una situazione decisamente insoddisfacente: non si sa se interrompere un'elaborazione inutile oppure attendere ancora un risultato che potrebbe essere fornito dopo un ulteriore lavoro in tempi accettabili.

È dunque importante poter stabilire se una MdT, o un altro sistema formale equivalente ("lambda-calcolo" di Church, ad es.), quando le si sottopone una stringa (di dati) si arresti o meno. Questo è detto problema della fermata o problema dell'arresto della macchina di Turing. Si trovano casi nei quali si dimostra o si verifica che si ha l'arresto, casi per i quali si dimostra che l'evoluzione non si arresta ma potrebbe procedere all'infinito e casi per i quali non si sa dare risposta.

Sembra ragionevole cercare un procedimento generale per decidere uno di questi problemi. Dato che le MdT si rivelano in grado di risolvere tutti i problemi che si sanno risolvere con gli altri procedimenti noti, è sensato chiedersi se esiste una macchina di Turing in grado di decidere per una qualsiasi coppia (M, d) costituita da una MdT M e da una stringa di dati d se, quando si fornisce d a M, questa si evolve fino ad arrestarsi o meno. Questa richiesta è resa ancor più significativa dall'esistenza, dimostrata dallo stesso Turing, di una cosiddetta macchina di Turing universale, macchina in grado di simulare qualsiasi evoluzione di qualsiasi MdT (anche le evoluzioni di se stessa!). Ebbene Turing ha dimostrato che la macchina di Turing universale non è in grado di decidere in ogni caso il problema dell'arresto. Quindi nessuna macchina di Turing può farlo. Questo risultato negativo si esprime dicendo che il problema dell'arresto è Turing-indecidibile. Se si accetta la congettura di Church-Turing sulla portata della macchina di Turing, si conclude che il problema dell'arresto della macchina di Turing è indecidibile.

Questo risultato negativo costituisce un limite per tutti i meccanismi computazionali; esso costituisce un risultato limitativo di grande importanza generale e per lo studio degli algoritmi. L'importanza generale dipende dal fatto che ogni procedimento dimostrativo automatico si trova equivalente a una computazione che può effettuarsi con una macchina di Turing. Va posto in rilievo che la Turing-indecidibilità del problema dell'arresto si dimostra equivalente al teorema di incompletezza di Gödel, il primo fondamentale risultato limitativo per la matematica. Si trova inoltre nello studio degli algoritmi e della loro complessità che dalla indecidibilità dell'arresto si deducono abbastanza agevolmente molti altri risultati limitativi.

Storia

Macchina computazionale

Modello di una parte dell'Analytical Engine di Babbage in mostra al Museo della scienza di Londra.

La nozione di "macchina computazionale" ha un'origine precedente ai lavori di Turing, Robin Gandy (1919–1995) - studente di Alan Turing (1912–1954) e successivamente amico per tutta la vita - ne tracciò la discendenza a partire da Charles Babbage (1834). Gandy a proposito della teoria di Babbage affermò:

(EN)

«That the whole of development and operations of analysis are now capable of being executed by machinery.»

(IT)

«Così l'interezza di sviluppare e di fare operazioni di analisi può essere ora eseguita da un macchinario»

L'analisi di Gandy della macchina analitica di Babbage ricava le seguenti operazioni:

(EN)

«

1. The arithmetic functions +, −, ×, where − indicates "proper" subtraction: x − y = 0 if y ≥ x.
2. Any sequence of operations is an operation.
3. Iteration of an operation (repeating n times an operation P).
4. Conditional iteration (repeating n times an operation P conditional on the "success" of test T).
5. Conditional transfer (i.e. conditional "goto").»

(IT)

«

1. Le funzioni aritmetiche +, −, ×, dove − indica la sottrazione "propria": x − y = 0 se y ≥ x.
2. Una qualunque sequenza di operazioni è un'operazione.
3. Iterazione di un'operazione (ripetere n volte un'operazione P).
4. Iterazione condizionata (ripetere n volte un'operazione P condizionata dal "successo" del test T).
5. Trasferimento condizionato (i.e. "goto" condizionato).»

Gandy sostiene che "le funzioni che possono essere calcolate da (1), (2) e (4) sono precisamente quelle calcolate da Turing.".

Cita inoltre altre "macchine di calcolo universale", incluse quelle di Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken (1937).

Costante fondamentale è programmare un numero fisso di sequenze di operazioni aritmetiche (anche se le importanti caratteristiche di interazione condizionata e trasferimento condizionato per la teoria di calcolo di una macchina non sono universalmente riconosciute).

Il problema della decisione (Entscheidungsproblem): il decimo problema di Hilbert

Nonostante il valore delle questioni poste dal famoso matematico David Hilbert nel 1900 sia innegabile, bisogna considerare che un aspetto del suo decimo problema andò alla deriva per almeno trent'anni senza essere impostato in maniera precisa. La formulazione originale di Hilbert per il decimo problema è la seguente:

(EN)

«10. Determination of the solvability of a Diophantine equation. Given a Diophantine equation with any number of unknown quantities and with rational integral coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers. The Entscheidungsproblem [decision problem for first-order logic] is solved when we know a procedure that allows for any given logical expression to decide by finitely many operations its validity or satisfiability... The Entscheidungsproblem must be considered the main problem of mathematical logic.»

(IT)

«10. Determinazione della risolvibilità di un'equazione diofantea. Data un'equazione diofantea in qualsiasi numero d'incognite e a coefficienti interi razionali: ideare un procedimento per mezzo del quale si possa stabilire, in un numero finito di operazioni, se l'equazione sia risolubile negli interi razionali. L'Entscheidungsproblem (problema della decisione per la logica del primo ordine) è risolto quando si arriva ad una procedura che permette di decidere attraverso un numero finito di espressioni la validità o soddisfabilità per qualunque espressione logica fornita. (...) L'Entscheidungsproblem dev'essere considerato il problema principale della logica matematica (...).»

Già nel 1922 questa nozione di Entscheidungsproblem venne sviluppata da Heinrich Behmann:

(EN)

«(...) most general form of the Entscheidungsproblem [is] as follows: A quite definite generally applicable prescription is required which will allow one to decide in a finite number of steps the truth or falsity of a given purely logical assertion... Behmann remarks that... the general problem is equivalent to the problem of deciding which mathematical propositions are true. If one were able to solve the Entscheidungsproblem then one would have a "procedure for solving many (or even all) mathematical problems".»

(IT)

«[...] la formula più generale dell'Entscheidungsproblem [è] come segue: È richiesta una prescrizione abbastanza definita, generalmente applicabile, tale da consentirci di decidere in un numero finito di passaggi verità o falsità di una data asserzione puramente logica. Behmann osserva: [...] il problema generale coincide con il problema di decidere quali proposizioni matematiche sono vere. [...] Se qualcuno fosse in grado di risolvere l'Entscheidungsproblem, allora avrebbe una "procedura per risolvere la maggior parte (o addirittura tutti) i problemi matematici".»

Nel 1928 presso il congresso internazionale dei matematici, Hilbert stesso "formulò la sua questione in modo abbastanza preciso. Primo, se la matematica sia completa, (...) secondo se sia consistente, (...) terzo se sia decidibile" (Hodges). Alle prime due domande rispose Kurt Gödel nel 1930 (nello stesso convegno in cui Hilbert pronunciò il suo discorso di commiato); il terzo - l'Entscheidungsproblem - dovette aspettare fino alla metà degli anni '30. Il problema stava nel fatto che una risposta richiedeva una definizione precisa di "prescrizione definita generalmente applicabile", o, come verrà chiamata dal professor Alonzo Church di Princeton, "calcolabilità effettiva", e nel 1928 non ne esisteva alcuna.

Tuttavia negli anni successivi Emil Post sviluppò una definizione per "un lavoratore in grado di spostarsi tra postazioni differenti, scrivendo e cancellando segni secondo una lista di istruzioni" (1936), ed analogamente fecero Church e alcuni suoi allievi (Stephen Kleene e J. B. Rosser) con il lambda calcolo e la teoria di Gödel sulle funzioni ricorsive primitive (1934). La relazione di Church (pubblicata nell'aprile del 1936) risolveva l'Entscheidungsproblem mostrandone l'indecidibilità, battendo sul tempo Turing (la cui teoria venne formulata nel maggio del 1936 ma pubblicata solo nel 1937). (Nel frattempo anche Post lavorò sul tema, collocandosi però nell'autunno del 1936, quindi successivamente a Turing). Il lavoro di Turing tuttavia si discosta nettamente dai lavori di Church e di Post, essendo caratterizzato dalla costruzione diretta di un'argomentazione che partiva dai principi fondativi della questione (Hodges).

La macchina di Alan Turing

Nella primavera del 1935 Turing, da giovane studente presso il King's College di Cambridge, accettò la sfida. Era stato stimolato dalle lezioni del logico Max Newman che lo introdusse al lavoro di Gödel e all'Entscheidungsproblem (problema della fermata), le ultime frontiere della conoscenza matematica. Newman impostò la questione sul concetto di "processo meccanico" come mezzo per analizzare il problema di Hilbert, una scelta fortemente criticata dalla comunità matematica inglese. Nel necrologio di Turing del 1955 Newman scrive:

(EN)

«To the question 'what is a "mechanical" process?' Turing returned the characteristic answer 'Something that can be done by a machine' and he embarked on the highly congenial task of analysing the general notion of a computing machine.»

(IT)

«Alla domanda "che cos'è un processo meccanico?" Turing rese la caratteristica risposta "Qualcosa che può essere fatto da una macchina" e intraprese il compito altamente congeniale di analizzare la nozione generale di macchina per il calcolo.»

(Gandy, p. 74)

Gandy scrive:

(EN)

«I suppose, but do not know, that Turing, right from the start of his work, had as his goal a proof of the undecidability of the Entscheidungsproblem. He told me that the 'main idea' of the paper came to him when he was lying in Grantchester meadows in the summer of 1935. The 'main idea' might have either been his analysis of computation or his realization that there was a universal machine, and so a diagonal argument to prove unsolvability (...)»

(IT)

«Suppongo, ma non lo so, che Turing, fin dall'inizio del suo lavoro, avesse come obiettivo quello di provare l'indecidibilità dell'Entscheidungsproblem. Mi disse che l'idea principale del documento gli venne in mente quando giaceva nei prati di Grantchester, nell'estate del 1935. L'idea principale potrebbe essere stata la sua analisi del calcolo, o la sua realizzazione che esisteva una macchina universale e quindi un argomento diagonale per dimostrarne l'insolvibilità (...)»

(Gandy, p. 76)

Il precoce interesse di Turing sulla macchina venne stimolato dalla macchina per scrivere della madre.

L'idea principale di Turing fu che l'Entscheidungsproblem di Hilbert potesse essere risolto attraverso un processo meccanico da una macchina (che successivamente venne teorizzata come la TM) e anche se gli giunse come illuminazione giovanile di una grande mente, in realtà aveva radici più profonde. Turing infatti per tutta la vita aveva dimostrato interesse nelle macchine, a partire dalle riflessioni infantili sulla macchina da scrivere della madre, che cercavano di estrapolarne le caratteristiche, che la determinavano appunto come macchina.

La sua tesi di dottorato, intitolata "Systems of Logic Based on Ordinals", contiene la seguente definizione di una "funzione calcolabile":

(EN)

«It was stated above that 'a function is effectively calculable if its values can be found by some purely mechanical process'. We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine. It is possible to give a mathematical description, in a certain normal form, of the structures of these machines. The development of these ideas leads to the author's definition of a computable function, and to an identification of computability with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions [the 3rd is the λ-calculus] are equivalent.»

(IT)

«È stato affermato in precedenza che "una funzione è effettivamente calcolabile se i suoi valori possono essere determinati mediante un processo puramente meccanico". Possiamo prendere questa affermazione alla lettera, intendendo per "processo puramente meccanico" quello che potrebbe essere eseguito da una macchina. È possibile fornire una descrizione matematica, in una certa forma normale, delle strutture di queste macchine. Lo sviluppo di queste idee porta alla definizione dell'autore di funzione calcolabile e all'identificazione del concetto di calcolabilità con quello di calcolabilità effettiva. Non è difficile, anche se un po' laborioso, dimostrare che queste tre definizioni [la terza è il λ-calcolo] sono equivalenti.»

(Turing (1939) in The Undecidable)

Quando Turing tornò in Inghilterra, dopo un periodo di formazione presso il college di Princeton, venne impiegato in ambito bellico dal governo inglese nella missione di infrangere i codici segreti tedeschi creati dalla macchina crittografica Enigma.

Venne poi coinvolto nella progettazione dell'ACE (Automatic Computing Engine): "la proposta ACE [di Turing] era effettivamente autonoma e le sue radici non risiedevano nell'EDVAC [l'iniziativa degli Stati Uniti], ma nella sua stessa macchina universale" (Hodges). Continuando così a sviluppare gli argomenti sull'origine e la natura di ciò che è stato nominato da Kleene (1952) la "tesi di Turing".

Ma ciò che Turing dimostrò con il suo modello di macchina computazionale apparve in forma definitiva solo nel suo articolo "On Computable Numbers, with a Application to the Entscheidungsproblem" (1937). In questo scritto infatti, per la prima volta concettualizza quella che diventerà la macchina di Turing:

(EN)

«[that] the Hilbert Entscheidungsproblem can have no solution... I propose therefore to show that there can be no general process for determining whether a given formula U of the functional calculus K is provable, i.e. that there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is provable.»

(IT)

«[che] l'Entscheidungsproblem di Hilbert non può avere soluzione... Propongo, quindi, di mostrare che non può esserci un processo generale per determinare se una data formula U del calcolo funzionale K è dimostrabile, cioè che non può esserci nessuna macchina a cui, data in ingresso una qualsiasi U di queste formule, alla fine dirà se U è dimostrabile.»

(Turing (1939) in The Undecidable)

1937–1970: Il "computer digitale", la nascita dell'"informatica"

Nel 1937 a Princeton, mentre stava lavorando alla sua tesi di dottorato, Turing costruì dal principio un moltiplicatore elettrico, realizzando i propri trasmettitori elettromeccanici. "Il compito di Alan era quello di incarnare la progettazione logica di una macchina Turing in una rete di trasmettitori azionati a interruttori...". Mentre Turing all'inizio sembrava essere solamente curioso, altri stavano andando nella stessa direzione sia in Germania (Konrad Zuse, 1938), che negli Stati Uniti (Howard Aiken e George Stibitz, 1937); i frutti delle loro fatiche furono usati dai militari dell'Asse e degli Alleati nella seconda guerra mondiale.

Nella prima metà degli anni '50 Hao Wang e Marvin Minsky ridussero la macchina Turing a una forma più semplice (un precursore della macchina sviluppata poi da Martin Davis); contemporaneamente anche i ricercatori europei stavano riducendo il nuovo computer elettronico a un oggetto teorico simile a quello che veniva chiamata "macchina di Turing".

Alla fine degli anni '50 e all'inizio degli anni '60, gli sviluppi paralleli e coincidenti di Melzak e Lambek (1961), Minsky (1961) e Shepherdson e Sturgis (1961) portarono avanti il lavoro europeo e ridussero la macchina di Turing a un computer più intuitivo, simile ad un modello astratto chiamato "contatore macchina"; Elgot e Robinson (1964), Hartmanis (1971), Cook e Reckhow (1973) svilupparono ancora il progetto con la "macchina a registro" e i modelli di "macchina ad accesso casuale" — ma fondamentalmente tutti sono "macchine di Turing multi-nastro" con aggiunti set di istruzioni aritmetiche.

1970-oggi: la macchina di Turing come modello computazionale

Oggi, le macchine per il calcolo, la registrazione e l'accesso casuale e la loro procreatrice macchina di Turing, continuano ad essere i modelli di scelta per i teorici che studiano questioni riguardanti la teoria della computazione. In particolare fa uso della macchina di Turing la teoria della complessità computazionale.

In base agli oggetti da manipolare nella computazione (numeri interi non-negativi o stringhe alfa-numeriche), due modelli hanno ottenuto una posizione dominante nella teoria basata sulle macchine complessa: la TM multinastro off-line e la RAM (random access machine) di Cook e Reckhow anche se quest'ultima assume un ruolo principale solamente nelle aree relative all'analisi degli algoritmi.

Varianti della macchina di Turing

In questo paragrafo le maggiori varianti della MdT definita in precedenza vengono presentate in termini discorsivi, lasciando ad articoli specifici le considerazioni più precise e complete.

Macchina di Turing multinastro

La MdT con più nastri differisce dalla classica sostanzialmente per il tipo della funzione di transizione; questa nel caso dei 3 nastri ha la forma

$\delta ~:~S\times A\times A\times A\to S\times A\times \{-1,0,+1\}\times A\times \{-1,0,+1\}\times A\times \{-1,0,+1\}$.

Questa funzione si fa dipendere dalla transizione da quanto viene letto sulle caselle su cui si trovano le testine relative ai diversi nastri e stabilisce quali caratteri devono essere modificati sui vari nastri e come si devono eventualmente spostare le testine.

È abbastanza evidente come questa macchina sia più semplice da usare della classica. Ad es. con essa si possono agevolmente copiare stringhe da un nastro all'altro e con porzioni di nastro si possono rendere disponibili sequenze di memorie indirizzabili abbastanza agevolmente. Con una macchina a tre nastri si può implementare molto facilmente un'operazione aritmetica come la somma di due numeri espressi mediante cifre decimali. Similmente e con gli opportuni accorgimenti e con l'uso di altri opportuni registri, lo si può intuire, si riescono a implementare altre operazioni aritmetiche o su entità discrete.

Per dimostrare che una macchina a più nastri P ha la stessa portata di quelle ad un solo nastro si tratta di individuare una di queste, denotiamola M che consente di simularne le evoluzioni. Questa simulazione viene effettuata simulando su un solo nastro della M i molti nastri della P. Si possono avere configurazioni della M che simulano configurazioni della P utilizzando scritture particolari che separano le aree nelle quali sono riprodotti i diversi nastri della P e segnalano le posizioni sulle quali si trovano le varie testine di I/O. A ciascun passo della P si fa corrispondere una serie di passi della M con i quali si sistemano i vari nastri e le posizioni delle relative testine. Si può capire come con un gran numero di spostamenti e di cambiamenti di stato si possono simulare le mosse della P.

Macchina di Turing con memoria bidimensionale

Consente di simulare abbastanza facilmente macchine a più nastri e di effettuare elaborazioni grafiche. Ulteriori varianti possono servirsi di memorie tridimensionali e simili.

Macchina di Turing non deterministica

La macchina di Turing non deterministica si distingue da quella deterministica definita in precedenza per il fatto che, in presenza di un determinato stato e di un determinato carattere letto, essa permette più transizioni.

Definizione

Una macchina di Turing non deterministica $T$, con grado di non determinismo $n$, è così definita:

$T=\langle S,s_{0},F,A,\beta ,n,\delta \rangle \quad$

dove le sole differenze rispetto alla definizione iniziale riguardano la presenza dell'intero $n$ e il genere della funzione di transizione:

$\delta ~:~S\times A\to S\times (A\times \{-1,0,+1\})^{k}~{\mbox{ dove }}~k=1,2,...,n$

Le sue configurazioni consistono quindi di insiemi finiti di configurazioni deterministiche, la cui cardinalità potrebbe crescere illimitatamente con il procedere di un'evoluzione.

Le computazioni che essa è in grado di svolgere sono descrivibili come insiemi di computazioni sviluppati da repliche della MdT deterministica, repliche che potrebbero rendersi necessarie ad ogni passo dell'evoluzione. Si osserva che questa richiesta oggi non dovrebbe affatto stupire, in quanto realizzabile con le tecniche dei computer collegati in rete ed effettivamente realizzata nella prassi delle elaborazioni distribuite.

Equivalenza con la MdT classica

Dato che ogni macchina deterministica si può considerare una particolare macchina non deterministica, si tratta di dimostrare che con una macchina deterministica M si riesce a simulare il comportamento di una macchina non deterministica N. Più precisamente supponiamo che N sia una macchina ad un nastro e che la M sia una macchina che dispone di una memoria bidimensionale, memoria assimilabile alla disponibilità di più nastri il cui numero sia aumentabile. La macchina M riesce a simulare con ciascuno dei suoi stati gli stati multipli della macchina N e con i suoi molti nastri i singoli nastri replicati della N. Ad ogni passo della N la M fa corrispondere una serie di passi con i quali fa evolvere i diversi nastri che rappresenta nella sua memoria bidimensionale e, in corrispondenza a una transizione non deterministica di molteplicità k, replica il nastro interessato trasformandolo nei k nastri richiesti.

In questo modo si vede come la macchina M possa simulare la N. Si osserva che alcuni singoli passi della macchina non deterministica richiedono un gran numero di passi e di appositi stati della deterministica.

Equivalenza tra MdT a k nastri e MdT ad un nastro

La capacità computazionale di una MdT non dipende dal numero di nastri che essa utilizza; questo è possibile dimostrarlo attraverso la simulazione. Indichiamo con T_k la macchina di Turing a k nastri e con T quella ad un nastro. Scriviamo l'input della macchina T_k sulla macchina T ovviamente un simbolo per ogni cella, quando la macchina T leggerà il primo simbolo essa per eseguire una quintupla della macchina T_k avrà bisogno di leggere k caratteri ricordando ogni volta il k-esimo carattere letto; verificato che la quintupla può essere eseguita a questo punto riporterà indietro la testina di k celle e può procedere all'esecuzione della quintupla sovrascrivendo i k caratteri; a questo punto la testina si troverà sulla cella contenente l'ultimo carattere scritto. Gli ultimi passaggi da eseguire sono il cambio di stato interno e il movimento della testina. È facile notare come l'insieme degli stati di T ha cardinalità maggiore rispetto all'insieme degli stati di T_k.

Macchine di Turing semplificate

Le macchine di Turing possono essere ulteriormente semplificate, senza perdita di portata computazionale. Le semplificazioni possibili sono (non attuabili contemporaneamente):

1. nastro illimitato solo in una direzione;
2. alfabeto di soli due caratteri, uno dei quali il simbolo blank;
3. solo due stati.

La dimostrazione dell'equivalenza con la macchina definita inizialmente con quelle con le caratteristiche 2 e 3 costituiscono il primo teorema di Shannon.

Un ulteriore modello semplificato di MdT è quello di avere tre MdT che compiono operazioni elementari (scrittura del carattere 1, scrittura del simbolo blank, spostamento della testina a destra, spostamento a sinistra, nessuna operazione) e ottenere da queste una nuova MdT tramite composizione per diramazione.

Macchina di Turing universale

La Macchina di Turing universale è quella che calcola la funzione u, che a sua volta è in grado di simulare il comportamento di qualunque macchina di Turing. La funzione u prende in input una codifica della macchina M che si voglia eseguire (ovvero un numero che una volta decodificato fornisca il codice di M) e una codifica dei parametri iniziali ad M.

Confronto con le macchine reali

La macchina di Turing, nonostante sia una "macchina astrattamente definita", è un ottimo modello per descrivere le macchine reali. In seguito alcune argomentazioni:

1. Tutto ciò che un computer reale può computare, lo può fare anche una MdT. Per esempio: "Una macchina di Turing può simulare ogni tipo di subroutine trovato nei linguaggi di programmazione, incluse procedure ricorsive e ognuno dei parametri di passaggio del meccanismo conosciuti" (Hopcroft and Ullman). Anche un automa a stati finiti (FSA) sufficientemente capiente può imitare ogni computer reale, trascurando l'IO. Perciò, uno statuto sulle limitazioni della macchina di Turing sarebbe applicato anche ai computer reali.
2. La differenza sta solo nella capacità di una MdT di manipolare una quantità illimitata di dati. Comunque, dato un tempo finito, una MdT (come una macchina reale) può processare una quantità finita di dati.
3. Come una MdT, una macchina reale può allargare il suo spazio di archiviazione secondo necessità, acquisendo dischi aggiuntivi o altri sistemi di archiviazione.
4. Le descrizioni di programmi per macchine reali, usando semplici modelli astratti, sono spesso molto più complesse di descrizioni ottenute usando la macchina di Turing. Per esempio, una MdT può assumere poche centinaia di stadi descrivendo un algoritmo, mentre un automa a stati finiti deterministico (DFA) equivalente ne fornirebbe quadrillioni partendo da una macchina reale data. Questo rende le rappresentazioni del DFA impossibili da analizzare.
5. Le macchine di Turing descrivono algoritmi indipendentemente da quanta memoria utilizzano. Ogni macchina corrente possiede dei limiti di memoria contenuta, ma questi limiti possono essere ampliati nel tempo arbitrariamente. Le macchine di Turing ci permettono di produrre enunciati sugli algoritmi che (teoricamente) avranno valore eterno, indipendentemente da evoluzioni nell'architettura convenzionale della meccanica dei computer.
6. Le MdT semplificano i postulati degli algoritmi. Infatti algoritmi che girano su una macchina Turing-equivalente astratta sono generalmente più astratti delle loro controparti su macchine reali, perché hanno una precisione arbitraria delle tipologie di dati possibili e non devono mai tener conto di condizioni impreviste (inclusi, ma non solo, casi di memoria limitata).

Bibliografia

Libri

• A. Hodges, Alan Turing. Storia di un Enigma, Torino, Bollati Boringhieri, 1991 [1983].
• J. Hopcroft, J. Ullman (1979), Introduction to Automata Theory, Languages and Computation, Addison-Wesley ISBN 0-201-02988-X
  • Versione italiana: J. Hopcroft, R. Motwani, J. Ullman, Automi, linguaggi e calcolabilità, Pearson, 2003, ISBN 978-88-7192-552-3
• Douglas Hofstadter (1979), Gödel, Escher, Bach: an Eternal Golden Braid
  • Versione italiana: Godel, Escher, Bach: un'eterna ghirlanda brillante, Adelphi, Milano, 1990, ISBN 88-459-0755-4
• Arto Salomaa, Computation and automata, Cambridge University Press, 1985, ISBN 0-521-30245-5
• Ivor Grattan-Guiness, The search for Mathematical Roots, 1870-1940, Princeton University Press, 2000, ISBN 0-691-05858-X
• (EN) Jackson, Philip C., Introduction to artificial intelligence, 1985.
• Arbib, Michael A., La mente, le macchine e la matematica.
• Davis, Martin, Il calcolatore universale, Milano, Adelphi, 2003, ISBN 9788845917929.
• Cappuccio, Massimiliano, Alan Turing: L'uomo, La macchina, L'enigma, Milano, AlboVerso, 2005, ISBN 88-89130-29-6.
• Stillwell, John, Da Pitagora a Turing, Bologna, ETS, 2018, ISBN 978-884675042-6.
• Martin Davis, The Undecidable, Dover Pubns; Dover edizione, 2004, ISBN 0486432289.
• Robin Gandy, The Confluence of Ideas in 1936, 1988.
• (EN) Marvin Minsky, capitolo 8, sez. 8.2 Unsolvability of the Halting Problem, in Computation: Finite and Infinite Machines, Prentice–Hall, Inc., 1967.
• (EN) Harold S. Stone, Introduction to Computer Organization and Data Structures, 1ª ed., New York, McGraw–Hill Book Company, 1972, ISBN 0-07-061726-0.

Articoli

• Alan Turing (1936): On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc., 42 pp. 230–265 Accessibile anche in linea

Voci correlate

• Alacre castoro
• Filosofia della matematica
• Informatica quantistica
• Macchina a stati
• Macchina di Turing probabilistica
• Macchina RAM
• Macchina RASP

Macchine equivalenti alla MdT

• Formica di Langton
• Gioco della vita

Altri progetti

Altri progetti

• Wikiversità
• Wikimedia Commons

• Wikiversità contiene risorse sulla macchina di Turing
• Wikimedia Commons contiene immagini o altri file sulla macchina di Turing

Collegamenti esterni

• Mauro Cappelli, macchina di Turing, in Enciclopedia della scienza e della tecnica, Istituto dell'Enciclopedia Italiana, 2007-2008.
• Turing, macchina di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Turing machine, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Macchina di Turing, su Stanford Encyclopedia of Philosophy.
• (EN) Eric W. Weisstein, Macchina di Turing, su MathWorld, Wolfram Research.
• (EN) Denis Howe, Macchina di Turing, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• (EN) Turing Machine nella Stanford Encyclopedia of Philosophy
• Andrea de Prisco, Algoritmi e Macchine di Turing (JPG), in MCmicrocomputer, n. 59, Roma, Technimedia, gennaio 1988, p. 120, ISSN 1123-2714.
• Articolo divulgativo, su startmag.it.

Simulatori

• Scritto in Python qui
• Scritto in JavaScript: JSTMSimulator (codice su GitHub)
• Scritto in Java: l'applet e il codice
• Scritto in Objective C per iPad: [1]