MdT5JFx - Simulatore Multimediale della Macchina di Turing
|
MdT5JFx - Simulatore Multimediale della Macchina di Turing |
| |
Come è fatta una MdT?
Una MdT è definita da:
un nastro infinito
una testina di lettura/scrittura
un'unità di controllo
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.
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.
