| |
Le Macchine di Turing come modello computazionale
Uno dei primi modelli computazionali ad essere stato proposto è quello
dovuto al matematico e logico inglese Alan Turing.
Nel 1936 Turing, nel tentativo di formalizzare la nozione di procedura
effettiva, analizzò il comportamento di un essere umano quando risolve un
problema di calcolo seguendo un metodo meccanico.
Egli riconobbe l'essenza
di tale attività nella capacità di scrivere su un foglio (grande
quanto necessario) usando un numero finito di simboli, con la possibilità
di riconsiderare il lavoro già svolto.
Per tenere traccia del lavoro già svolto, è opportuno non solo potere
rileggere i simboli scritti in precedenza sul foglio, ma anche potere avere
una sorta di stato mentale, influenzato da tutte le azioni precedenti e
in grado di condizionare le scelte successive.
Da questa analisi Turing dedusse che una macchina per computare dovesse
disporre:
- di un nastro infinito, suddiviso in celle, ciascuna capace di contenere un
qualunque simbolo;
- di una testina movibile, atta a leggere e/o scrivere quintupleil nastro;
- di una scatola nera, nota come controllo finito, per memorizzare lo
stato mentale corrente.
Le operazioni elementari che una tale macchina doveva essere in grado di
eseguire erano:
- cambiare il simbolo sotto la testina;
- spostare la testina in modo da agire su una delle celle adiacenti a quella
corrente.
Secondo Turing era inoltre necessario che, congiuntamente a tali operazioni,
la macchina fosse in grado di cambiare il proprio stato; pertanto assumeva
che, più in generale, la macchina dovesse essere in grado, a seconda dello
stato corrente e del simbolo letto dalla testina, di:
- cambiare il simbolo sotto la testina e lo stato corrente e spostare la testina di una cella.
Per consentire alla macchina di scegliere, in base alla situazione corrente,
quale azione eseguire, era necessario dotarla di un programma, inteso come
insieme di regole, dette quintuple, della forma (q1, a, b, M, q2) da
interpretare come segue:
Nello stato q1, leggendo il simbolo a, passa allo stato q2 e
scrivi il simbolo b sul nastro, poi sposta la testina a sinistra o a
destra o rimani inerte, a seconda che M sia S (Sinistra),
D (Destra) o I (Inerte).
Per descrivere la situazione in cui si trova una macchina di Turing in un
certo momento basta fornirne la Configurazione Istantanea, ovvero il
contenuto del nastro, la posizione della testina e lo stato corrente.
Nell'ambito di questo modello una computazione altro non è che una sequenza
di configurazioni istantanee, di cui la prima (detta Configurazione
Iniziale) codifica l'input e lo stato iniziale, mentre ogni altra
configurazione istantanea è ottenuta da quella immediatamente precedente
eseguendo, di volta in volta, l'unica quintupla applicabile.
Si noti che non necessariamente una tale sequenza è finita, poiché la
macchina si arresta solo quando nessuna quintupla può essere applicata: in
tal caso l'ultima configurazione (detta Configurazione Finale) è quella
che codifica l'output.
E' bene tener presente che esistono molte versioni (tutte computazionalmente
equivalenti) della macchina di Turing. Per esempio si puo' definire la Macchina
du Turing in modo che utilizzi quadruple anziche' quintuple.
Analizzando le caratteristiche della Macchina di Turing, si nota che
tale modello computazionale introduce, in maniera formale ma semplice e essenziale,
alcuni elementi tipici della programmazione imperativa, quali:
- locazione
- Le celle del nastro di una Macchina di Turing hanno la
stessa logica di funzionamento delle locazioni, in quanto contengono un valore
che può essere aggiornato in maniera distruttiva (ovvero sostituito senza
che sia possibile risalire al valore precedente).
- assegnamento
- Le quintuple del tipo (q1, a, b, M, q2), che sostituiscono
il simbolo a con il nuovo simbolo b, realizzano l'assegnamento del
valore b alla locazione corrispondente alla cella sotto la testina.
- memoria
- Data la corrispondenza fra celle e locazioni, il nastro non
è altro che una sorta di memoria lineare infinita ad accesso sequenziale,
nel senso che per poter accedere ad una determinata locazione è necessario
spostare la testina fino a raggiungere la cella corrispondente.
- stato
- Già nella definizione delle Macchine di Turing incontriamo
il concetto di stato, come elemento che condiziona le scelte che la macchina
opera durante il calcolo, e di configurazione, come descrizione della situazione
in cui la macchina si trova in un dato istante.
- iterazione
- una computazione, dato il numero finito di quintuple
avviene attraverso l'iterazione dell'"esecuzione" delle quintuple (che possono
venire interpretate come una sorta di istruzioni della macchina).
|