CHI ERA ALAN TURING?
Turing fece parte del team di
matematici che, a partire dalla
base di Bletchley Park,
decodificarono i messaggi
scritti dalle macchine tedesche
Enigma prima e durante il
secondo conflitto mondiale;
progettò primi particolari
modelli di macchine, che ne
hanno fatto uno dei pionieri
dell’intelligenza artificiale.
A lui si deve, nello specifico, l’ideazione, nel
1936, di un modello ideale di calcolo
concretamente applicabile, la cosiddetta
“Turing machine”, la cui particolare struttura
pone il suo inventore fra i precursori dei
costruttori di moderni computer.
Riportiamo di seguito un modello ideale della
macchina.
Una macchina di Turing (MdT) è definita da un insieme di
regole che definiscono il comportamento della macchina
su un nastro di input-output (lettura e scrittura).
Il nastro può essere immaginato come un nastro di carta
di lunghezza infinita, diviso in quadratini dette celle. Ogni
cella contiene un simbolo oppure è vuota. Una MdT ha una
testina che si sposta lungo il nastro leggendo, scrivendo,
oppure cancellando simboli nelle celle del nastro. La
macchina analizza il nastro, una cella alla volta, iniziando
dalla cella che contiene il simbolo più a sinistra del
nastro.
Ad ogni passo, la macchina legge un simbolo sul nastro e,
in accordo al suo stato interno corrente:
1- decide il suo prossimo stato interno
2- scrive un simbolo sul nastro
3-decide se spostare o meno la testina a sinistra o a
destra di una posizione.
Come per uno stato della mente di un
essere umano, lo stato interno di una MdT
definisce l’ambiente in cui una decisione
viene presa. Una MdT può avere solo un
numero FINITO di stati.
Il comportamento di una MdT può essere
programmato definendo un insieme di
regole, o quintuple, del tipo:
(stato interno corrente, simbolo letto,
prossimo stato interno, simbolo
scritto,direzione).
ESEMPIO: Consideriamo una MdT che modifica una
sequenza di A rimpiazzando ogni A in posizione dispari con
una B (la prima A ha posizione pari uguale a 0).
Definiamo questa macchina con il seguente insieme di
regole:
Stato interno
corrente
Simbolo
letto
Prossimo
stato interno
Simbolo
scritto
Direzione
0
A
1
A
>
1
A
0
B
>
0
-
FINE
-
-
1
-
FINE
-
-
La prima quintupla, ad esempio, stabilisce l’ azione che la
macchina deve eseguire
quando si trova nello stato interno 0 e il simbolo in lettura
è A.
Tale situazione corrisponde ad una A in posizione pari.
Ad esempio consideriamo la situazione iniziale in cui la sequenza di
ingresso è AA.
0
A
1
A
>
0
A
…
…
A
La macchina si trova nello stato interno iniziale 0 ed il simbolo in lettura è A
(pari).
La prima quintupla stabilisce che la macchina deve cambiare il suo proprio
stato interno in 1, scrivere il simbolo A sul nastro e spostarsi verso destra.
1
A
0
B
>
1
…
A
A
…
Adesso la macchina è nello stato 1 e il simbolo in lettura è B. In questa caso la
seconda regola stabilisce che la macchina torna nello stato zero, scrivendo il
simbolo B e spostandosi a destra ottenendo la nuova configurazione.
0
-
FINE
-
0
A
…
…
B
Secondo la terza regola, la macchina che si trova nello stato 0,
trova la casella bianca e si sposta nello stato FINE; la macchina
non scrive simboli e si ferma.
1
-
FINE
-
FINE
…
A
B
…
E infine vi proponiamo un semplice esempio di
una macchina di Turing che cambia le O con le
A e le I con le E.
PER VISUALIZZARE IL
LAVORO DELLA MdT
PREMERE IL TASTO
INVIO
Stato interno
corrente
Simbolo
letto
Prossimo
stato interno
Simbolo
scritto
Direzione
0
O
N
C-I
FINE
0
N
A
C
E-
>-
Progetto realizzato da:
Lamanna Claudia
Laguardia Valentina
Rotolo Viviana
Simone Viviana
Prof.essa De Blasi Gabriella
Classe 3^ A scientifico tecnologico