1.1        Macchina di Turing

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#

Figura 2.471

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 ).

-- % ML statements 

-- MdT inputs: input ...

-- states name I O M S where

--             I = input symbol

--             O = output symbol

--             M = move (Right, Left)

--             S = next stato state

-- S0 = starting state, hlt halt state

-- first memory cell must contains 0

-- number rappresentation: n is n+1 consecutives 1

% (* include some list functions *)

% use "listfunc.sm";

% (* sample input *)

% val l1 = [0,1,1,1,1,1,1,0,1,1,1,1]; (* number 5 3 *)

% (* add *)

S0 0 0 R S0 S0 search starting number

S0 1 1 R S1

S1 1 1 R S1

S1 0 0 R S2 end first addendum

S2 0 0 R S2 skip internumbers

S2 1 1 R S3 chek if > 0

S3 1 1 L S4

S3 0 0 L S5

S5 1 0 L hlt erase

S4 1 0 L S6 -1 at second addendum

S6 0 0 L S6 search end of first addendum

S6 1 1 R S7

S7 0 1 R S2