David Hilbert, Matematico Logico
Nel Congresso Internazionale di Parigi del 1900 David
Hilbert propose 23 problemi matematici che apparivano
insolubili. Uno di questi problemi prevedeva la
dimostrazione della coerenza dell’aritmetica dei numeri
reali. Successivamente nel 1928 Hilbert riformula il
problema e lo divide in 2 parti:
- La matematica è completa? – Ovvero, per ogni formula
valida dimostrabile dall’esterno, si può dimostrare la
validità della formula anche all’interno di un sistema
formale?
- La matematica è decidibile? – Ovvero, esiste un
algoritmo che stabilisca la validità di qualsiasi
enunciato all’interno di un sistema formale? La ricerca
di questo procedimento è nota come l’Entscheidungsproblem
(problema della decisione).
La prima parte del problema fu risolta da Kurt Gödel nel 1931. Gödel riuscì a scoprire una proposizione vera ma non dimostrabile all’interno del sistema, ciò comportava l’incompletezza di ogni sistema logico abbastanza potente da comprendere l’aritmetica. Questo risultato distrusse il programma di Hilbert, ma non tutto era perduto, restava ancora il problema della decisione da risolvere.
Kurt Gödel
Affascinato da queste novità Max Newman tenne un corso sui fondamenti della matematica che terminava con il teorema di Gödel. Turing, frequentando il corso, venne a conoscenza del problema della decisione e cominciò subito a lavorare alla dimostrazione dell'insolubilità del problema.
Cerchiamo ora di ripercorrere i passi compiuti da Turing che lo portarono a porre le basi teoriche della macchina universale e risolvere il problema della decisione.
On computable Numbers, with an application to the Entscheindungsproblem
Turing inizia analizzando il procedimento che ogni essere umano compie quando sta eseguendo un qualsiasi algoritmo(addizione, moltiplicazione, etc...), e ne estrapola le parti fondamentali. Successivamente capisce che tutte le azioni svolte da una persona possono essere eseguite da una macchina. La macchina descritta da Turing non nasce come una macchina da costruire (anche se è possibile farlo, ovviamente senza il nastro infinito!), ma piuttosto è una macchina ipotetica che ci insegna le potenzialità e i limiti della nozione di computabilità definita da Turing, quella che ancora oggi utilizziamo come base teorica del funzionamento dei computer.
Questa macchina, oggi conosciuta come macchina di Turing, ha un numero limitato di configurazioni e lavora su un nastro diviso in celle, ognuna delle quali può contenere un simbolo. In ogni momento la macchina legge solamente un simbolo alla volta ma, alterando le diverse configurazioni, è in grado di ricordare simboli precedentemente visti. Le azioni della macchina sono determinate dalla configurazione attiva e dal simbolo letto, esse possono comprendere:
- Scrittura di un nuovo simbolo
- Cancellazione di un simbolo
- Spostamento di una cella a destra o a sinistra
- Cambio di configurazione
Macchina di Turing
L’insieme delle configurazioni di una macchina è chiamata
tavola di comportamento.
Ogni macchina di Turing è
costituita da una specifica tavola di comportamento.
Esempio di tavola di comportamento
| Configurazione attuale | Simbolo letto | separatore | Nuovo simbolo | Spostamento | Nuova configurazione |
|---|---|---|---|---|---|
| A | 0 | : | 1 | Destra | B |
| B | 1 | : | 0 | Destra | A |
Vediamo ora il comportamento di una macchina di Turing T che si occupa dell’addizione di due numeri scritti in forma unaria.
Tavola di comportamento T
| A | 1 | : | * | Destra | A |
| + | : | 1 | Destra | A | |
| 0 | : | * | Sinistra | B | |
| B | 1 | : | 0 | * | B |
| 0 | : | * | Halt | B |
Nastro
 | | | | | | | |
| Stato Iniziale | 1 | 1 | 1 | + | 1 | 1 | 0 |
| | | | | | ||
| Stato Finale | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
Dopo aver introdotto il funzionamento della macchina,
Turing applica un procedimento, molto simile a quello usato
da Gödel, per codificare la tavola di comportamento in una
stringa di lettere e successivamente in una sequenza di
numeri naturali che prende il nome di numero di
descrizione. Questa codifica crea una relazione tra i
numeri naturali e le macchine di Turing.
Numero di descrizione della macchina di
Turing T:
919801864663661691977919800064680186169197791980086466366269297792980186468008636929779298008646636636939
Utilizzando i numeri di descrizione e il metodo della
diagonale, scoperto da George Cantor, Turing riesce a
dimostrare che non esiste un algoritmo per verificare la
validità di qualsiasi enunciato. Il problema della
decisione è di conseguenza insolubile. Tuttavia, per
ottenere un’ulteriore prova dell’insolubilità del problema
della decisione, introduce la macchina universale di
Turing.
La macchina universale di Turing
"It is possible to invent a single machine which can
be used to compute any computable sequence."
Alan
Turing, On computable numbers... , 1936.
L’idea geniale della macchina universale è quella di trattare dati e programma nello stesso modo. Turing dimostra che esiste una macchina di Turing, denominata macchina universale di Turing, in grado di leggere il numero di descrizione di una qualsiasi macchina di Turing e successivamente di emulare le azioni che quella macchina avrebbe eseguito con un qualsiasi dato in input.
| Numero di descrizione macchina di turing T | | | Ingresso dati a T |
La maggior parte dei dispositivi elettronici programmabili, da computers a smartphones, lavorano con lo stesso principio utilizzato dalla macchina universale di Turing. Possiamo quindi capire l’influenza che, le idee di Turing, hanno avuto sul nostro secolo.