Nel 1936 Alan Turing propose un modello di automa per provare che qualsiasi algoritmo che un uomo può eseguire, può essere eseguito “meccanicamente” eseguendo un’insieme di istruzioni.
Nel modello più semplice la MdT è formato da una memoria a celle contigue
illimitata, e da un insieme di stati, fra cui uno iniziale ed uno o più stati
finali. La memoria contiene inizialmente i dati di entrata e una “testina di
lettura/scrittura” è posizionata sulla prima cella di memoria. Il tutto è
governato da una funzione che data una coppia stato simbolo indica il
simbolo che sostituisce, lo spostamento in memoria a destra o sinistra e lo
stato successivo.
Formalmente una possibile definizione di MdT
è M = (K, Σ, est, s)
dove:
·
K = {q0,
q1,
...} c'est un insieme di stati, fra i quali lo stato in cui la macchina si
arresta,
·
Σ =
{#, |}
l’alfabeto, cioè l’insieme di simboli présenti in memoria, #
denota uno spazio, una sequenza di n | denota il numero n-1,
·
s ε
K lo stato iniziale,
·
Ф una funzione
di transizione che associa ad una coppia {simbolo, stato}, un nuovo stato, il
simbole sostituente e lo spostamento sulla memoria: K x Σ
à (K U
hlt) x (Σ U
{L, R})
Essenzialmente la macchina, in un certo stato qi legge il simbolo i, scrive il simbolo j, sposta la testina di lettura/scrittura di una posizione a destra o a sinistro e passa nello stato qj.
Per specificare un MdT per un algoritmo di
calcolo, è sufficiente fornire la funzione di transizione, per esempio nella
Figura
2.47‑1
sono descritte le MdT che calcolano le funzioni ricorsive di base:
la funzione f0(Xn)
= 0, la funzione proiezione fi(Xn)
= xi, e la funzione successore s(x) = x +
1.
|
Funzione |
Funzione di transizione |
Esempi:
input |
output |
|
Constante 0 |
S0 1 # D S0 S0 # # D S1 S1 # 1 D hlt S1 1 # D S0 |
111#1#11## 1## 111#1#11111## |
#########1 ##1 ############1 |
|
Proiezione |
S0 1 # D S1 S1 1 1 D
S3 elimina numero S1 # # D
S10 via il resto S3 # # D S3
S3 1 # D
S4 S4 1 # D
S4 S4 # # S
S5 indietro S5 # # S
S5 S5 1 1 S
S6 S6 # # D
S0 sono all’inizio S10 # # D
S10 S10 1 1 D
S11 S11 1 1 D
S11 S11 # # D
S12 S12 # # D
hlt S12 1 # D
S13 S13 1 # D
S13 via il resto S13 # # D S12 |
1#11#111#11111 1#1111111111111#1 11#1111#111#1111#11 (L’input
contiene l’indice della funzione – 1 seguito da n numeri) |
##11 ##1111111111111 ########111 |
|
Successeur |
S0 1 1 D S0 S0 # 1 D hlt |
111111## 1## |
1111111# 11# |
Certe sequenze di transizione sono delle macchie generali, per esempio le due transizioni con stato S11 della funzione Proiezione, è la MdT che si posiziona a destra di un numero. Concettualemente sono un mezzo per semplificare la descrizione di una macchina, vista come un insieme di MdT che operano sequenzialmente.
Si dimostra che la composizione di funzioni, la recursione primitiva e la minimalizzazione non limitata sono calcolabili con MdT, e quindi la MdT può calcolare qualsiasi funzione o algoritmo (Tesi di Church).
Nel modello MdT Universale, stati ed istruzioni del calcolo sono codificati insieme ai dati di entrata. La MdT Universale è il modello dei computer moderni, in essi la memoria contiene infatti le istruzioni eseguite dall'unità di calcolo ed i dati oggetto delle istruzioni.
Esistono diverse varianti della Macchina di Touring, tutte equivalenti per potere di calcolo.
L’esempio sottostante è la MdT per calcolare la somma di due numeri, il sorgente è opportunamente commentato, i simboli dell’alfabeto sono {0,1}, ed è utilizzato da un programma Dustyscript (Dustyscript par. 2.24 )per generare il sorgente dell’interprete della MdT in ML (ML par. 2.50 ).