Macchina di Turing
Nel 1936 Turing scrisse un articolo intitolato On computable numbers with an application to the Entscheidungsproblem, in risposta alla sfida lanciata da Hilbert nel 1928: l'entscheidungsproblem o problema della decidibilità .
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 brutale.
Una prima forte risposta la diede il matematico boemo Gödel in occasione della conferenza sull'epistemologia delle scienze esatte di Könisberg(1931), 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.
"Un giovane sconosciuto di nome Alan Turing risolse il quesito quasi per gioco. Con una macchina immaginaria." (si veda [1]).
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 t1, la macchina si trova in uno stato interno s1 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
- una configurazione iniziale, per t=t0 (prima dell'esecuzione del programma)
- una configurazione finale, per t=tn (al termine dell'esecuzione del programma)
- delle configurazioni intermedie, per t=ti (prima dell'esecuzione dell'istruzione oi)
- 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
Eseguire un'operazione o1, tra gli istanti di tempo t1 e t2, vuol dire passare dallo stato interno s1 al s2. Più formalmente questo si esprime in simboli come: {s1,a1,o1,s2} da leggersi come: nello stato interno s1 la macchina osserva il simbolo a1, esegue l'operazione o1 e si ritrova nello stato interno s2.
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 parente stretta della 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.
Approfondimenti
