MACCHINE di TURING
Il concetto di algoritmo (ossia "procedimento meccanico di calcolo") è usato intuitivamente
sin dalla antichità, ma solo all'inizio del XX secolo viene messa
a fuoco l'esigenza di formalizzarlo, in relazione a vari aspetti:
– nello sviluppo dei primi sistemi formali si richiede che le regole di derivazione siano "meccaniche",
... in modo, ad es., da poter controllare in modo oggettivo se una dimostrazione è corretta o no;
– nei primi tentativi di definire il concetto di casualità si incappa nel
problema di precisare (per contrasto) quali siano i procedimenti "meccanici";
– il fattore scatenante è, però, più
specificamente, la necessità di dare alcune risposte ad alcuni problemi
di risolviblità algortimica (esiste un algortimo per calcolare la
soluzione di un certo problema?), sorti sia nell'ambito della teoria dei
numeri che in quello della nascente logica matematica (decidere se una
formula è un teorema o no, ...): per stabilire delle risposte negative
(non esiste alcun algortimo che ...) occorre aver definito che cosa è
un algortimo.
L'idea avuta da Turing (vedi), e più o meno contemporaneamente da Post, fu quella di cercare di formalizzare matematicamente il concetto di calcolatore. A noi può sembrare un'idea non particolarmente originale, ma occorre tener conto che si era intorno al 1930, 15 anni prima che nascessero i primi computer.
Turing analizzò il concetto di algortimo, interpretandolo come un procedimento computazionale svolto dall'uomo, e ne individuò gli aspetti essenziali (non è necessaria la bidimensionalità del foglio, basta leggere/scrivere un simbolo per volta, ...). Alla fine (siamo nel 1936) lo precisò descrivendolo mediante un opportuno modello: un nastro suddiviso in celle potenzialmente illimitato, una quantità finita di simboli, un simbolo per cella, una "testina" di lettura/scrittura che può osservare (ossia, operare una scansione di) una cella per volta, può scrivervi un simbolo e spostarsi a sinistra o a destra di una cella per volta.
Vediamo l'idea di macchina porgrammabile messa a punto da Turing in una versione intermedia tra la versione originale e quella messa a punto da Post, a noi più facile da comprendere (questa versione fu presentata da Martin Davis in "What is a computation?", nel famoso libro "Mathematics Today" curato - nel 1978 - da Lynn Arthur Steen; chi è interessato ad approfondimenti può vedere qui).
Simboli sul nastro: solo 0 e 1
Programma: lista di istruzioni dei tipi seguenti (la semantica è descritta tra parentesi):
print 0 (scrivi 0 nella cella su cui sei posizionato e passa alla istruzione successiva)
print 1 (scrivi 1 nella cella su cui sei posizionato e passa alla istruzione successiva)
go left (spostati nella prima cella a sinistra e passa alla istruzione successiva)
go right (spostati nella prima cella a destra e passa alla istruzione successiva)
go to step N if 1 is scanned (se sei su un 1 vai alla istruzione n-esima)
go to step N if 0 is scanned (se sei su uno 0 vai alla istruzione n-esima)
stop (fermati)
Convenzione su input e output:
• la testina di lettura è inizialmente posizionata all'inizio della stringa
di input (massima porzione del nastro nella sua configurazione iniziale
che ha "1" come primo e ultimo carattere);
• il programma termina quando arriva alla istruzione stop o quando ha eseguito l'ultima istruzione o
dovrebbe passare a un'istruzione che non è nell'elenco.
| Esempio. Il programma a lato se la stringa di input è
"11" (o una qualunque altra stringa costituita non da un solo "1") si ferma,
mentre se la stringa di input è "1" continua ad spostare la testina
di lettura a destra, girando senza fine sulle prime due istruzioni. Volendo, potrei non mettere stop. Se indico con n la stringa costituita da n+1 "1" posso dire che il programma calcola la funzione a 1 input e 1 output che a n positivo associa n stesso e che non è definita in 0. |
go right
stop |
| Il programma a lato, invece, calcola la funzione predecessore, definita solo per input positivi. Infatti si sposta a destra e se incontra ancora un "1" torna indietro sull"1" inziale e lo sostituisce con uno "0", e si arresta. Se invece incontra "0" continua senza fine a spostarsi a destra. | go right
go left print 0 |
Analogamente posso rappresentare la coppia 3,2 e la terna 3,0,2 con le stringhe 11110111 e 1111010111: ogni numero naturale n con n+1 "1" e il separatore con uno "0".
Altri esempi di programmi di Turing-Post, in cui aggiungo i numeri delle istruzioni (che non fanno parte del programma) per facilitare la lettura.
| Addizionatore. Idea: tolgo due "1" e trasformo in "1" lo "0" di separazione; se c'è un solo "1" prima di "0" mi limito a togliere questo "1": "111011", cioè (2,1), viene trasformato in "1111", cioè 3. | 1 print 0
2 go right 3 go to step 8 if 0 is scanned 4 print 0 5 go right 6 go to step 5 if 1 is scanned 7 print 1 8 stop |
||
| |||
| 1 print 0
2 go left 3 go to step 2 if 1 is scanned 4 print 1 5 go right 6 go to step 5 if 1 is scanned 7 print 1 8 go right 9 go to step 1 if 1 is scanned 10 stop |
Duplicatore (duplica stringhe di 1, ovvero a N associa 2N+1). Idea: man mano cancello un "1", ne aggiungo "1" a sinistra e lo riscrivo, poi mi sposto a destra e faccio lo stesso con un nuovo "1". |
Tutte le altre formalizzazioni del concetto di algoritmo messe a punto più o meno negli stessi anni sono risultate essere equivalenti a questa. E tutti gli algortimi messi a punto nell'ambito della matematica sono risultati rappresentabili mediante programmi di Turing-Post. Possiamo, quindi, assumere questa come definizione di algortimo (l'assunzione di questa descrizione del concetto di algoritmo come sua definizione è nota come tesi di Church).