Premessa
Lo studio della
Macchina di Turing è previsto quasi all'inizio del
programma di Informatica nella
terza classe dell'indirizzo
Programmatori Mercurio.
Pur riconoscendo
l'alta valenza didattica
dell'argomento, non sempre decidevo
di
svolgerlo
durante la mia esperienza di
insegnamento, sia per la
valutazione della complessità e
quindi dei problemi che esso
avrebbe potuto provocare in
qualche classe specifica, sia per
le oggettive difficoltà che si
incontrano nell'utilizzare tale
formalismo per la risoluzione dei
problemi, aiutandosi con strumenti
didattici tradizionali come
lavagna e gesso.
Spinto da queste considerazioni
nel 1996, iniziavo a realizzare
con "Toolbook" un simulatore
multimediale, che potesse essere
utile nelle diverse fasi previste
per lo studio e per l'utilizzo in
laboratorio della
Macchina di Turing .
Successivamente, continuavo a
svolgere l'argomento di solito a
classi terze alterne, valutando il
livello di apprendimento delle
stesse ed aggiornando, di volta in
volta, con nuove funzioni, la
versione del simulatore.
Da alcuni anni, dopo aver notato il
forte interesse suscitato
dall'argomento nella maggioranza
degli studenti e le evidenti
facilitazioni che l'utilizzo del
simulatore induce nella comprensione
dei concetti di base
dell'Informatica, del funzionamento
del calcolatore e delle tecniche di
programmazione, dedichiamo alla
Macchina di Turing un adeguato
periodo di tempo che comprende tutta
la fase di studio e l'utilizzo
in laboratorio del simulatore per la
risoluzione di problemi, fino a
quando non iniziamo a scrivere i
primi programmi utilizzando un
linguaggio di programmazione.
Che cosa è
una macchina di
Turing?
Nel 1936 il
matematico inglese Alan
Turing propose l'idea di
una macchina astratta che
fosse capace di eseguire
ogni tipo di calcolo su
numeri e simboli.
La
tesi di Church postula che
la classe delle funzioni
calcolabili, secondo il
concetto intuitivo di
algoritmo, coincide con la
classe delle funzioni
Turing-calcolabili cioè
calcolabili con una
Macchina di Turing.
Come è fatta
una MdT?
Una MdT
è definita da:
Il nastro infinito
Il
nastro infinito che può essere considerato
come il supporto di memorizzazione delle
informazioni (memoria esterna) è suddiviso in
celle, in una cella può essere contenuto un
simbolo preso da un alfabeto opportuno; un
alfabeto è semplicemente un insieme di simboli
che comprende anche il blank che corrisponde
alla cella vuota.
La testina di lettura/scrittura
La
macchina è dotata di una testina di
lettura/scrittura in grado di leggere e
scrivere il contenuto della cella del nastro
su cui si trova;
L'unità di controllo
La
macchina è dotata di un'unità di controllo che
evolve attraversando un insieme finito di
stati interni, a partire da uno stato iniziale
fino a raggiungere uno stato finale. Lo stato
interno rappresenta una situazione in cui si
trova la macchina durante l'esecuzione e 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.
Come funziona
una MdT?
Il comportamento
della macchina durante l'esecuzione
La
macchina analizza il nastro, una
cella alla volta, iniziando dalla
cella su cui è posizionata la
testina.
Ad ogni passo, la macchina legge un
simbolo sul nastro e in accordo col
suo stato interno corrente:
-
determina il suo
prossimo stato interno
-
scrive un simbolo sul
nastro
-
decide se spostare o
meno la testina a sinistra o a
destra di una posizione
Il programma di una MdT
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
testina).
Ciascuna
quintupla associa ad ogni
coppia:
stato-interno-corrente,
simbolo-letto
una
terna:
prossimo-stato-interno,
simbolo-scritto, direzione
testina.
Non può
esistere più
di una regola
che inizi con
una coppia stato-interno-corrente,
simbolo-letto.
Come
opera
una MdT
Vediamo adesso come una
MdT effettua i suoi calcoli.
Inizialmente il nastro contiene una
sequenza finita di simboli, detta sequenza
di ingresso. La MdT è nel suo
stato interno iniziale con la
testina posizionata su una cella del
nastro contenente un certo simbolo.
A partire da questa configurazione
iniziale, la MdT effettua una serie
di azioni (chiamate mosse) seguendo
rigorosamente il suo insieme di
regole. Se la macchina raggiunge uno
stato interno per cui non
esiste nessuna quintupla per la
coppia:
stato-interno-corrente,
simbolo-letto
allora
la MdT si
ferma e
termina la sua
computazione.
In
particolare:
-
Determina la
regola da
applicare in
base allo
stato interno
e al simbolo
corrente
(quello letto
dalla testina)
-
Se
esiste una
tale regola
cambia lo
stato, scrive
il simbolo
sulla cella
corrente si
sposta come
indicato dalla
regola (Questo
passaggio da
una
configurazione
a quella
dell'istante
successivo si
chiama mossa
della MdT)
-
Se non
esiste la
regola
l’esecuzione
termina.
Esempio:
cambiamo A in
B
Vogliamo
programmare
una Macchina
di Turing che,
dato sul
nastro di
input una
stringa di A e
B, rimpiazza
ogni
occorrenza di
A in B e
viceversa
Assumendo che
la testina sia
posizionata
sul primo
simbolo della
stringa
dobbiamo
cambiare una A
in B (o
viceversa)
spostare la
testina sul
prossimo
carattere
Cambiamo A in
B (continua)
Le regole
corrispondenti
sono:
(q0, A, q0, B,
d)
(q0, B, q0, A,
d)
In questo caso
è sufficiente
lo stato q0
Al termine
della stringa
l’esecuzione
sarà arrestata
poichè non
esiste una
quintupla che
inizia con la
coppia q0,
blank.
Nuova
Versione del Simulatore Multimediale
MdT5JFx |
Simulatore della Macchina
di Turing
Esistono
molti programmi "simulatori" di macchine
di Turing, ovvero programmi capaci di
simulare
il comportamento di una macchina di Turing
mostrandone il comportamento sullo schermo
di un calcolatore.
MdT5 è un
simulatore multimediale della Macchina
di Turing cioè un programma che
permette di definire una Macchina di Turing e di
simulare il suo comportamento durante il
funzionamento utilizzando per la rappresentazione un
modello multimediale. Il simulatore
è stato realizzato con "Toolbook" ed è utilizzato
dagli studenti del Corso Programmatori Mercurio
dell'I.T.C.G. "Umberto I" di Ascoli Piceno.
Nuova
Versione del Simulatore Multimediale
MdT5JFx |
|
