Documentazione
Guida operativa
MdTJFx contiene un sistema di controllo integrato che guida l'utente nella definizione della Macchina di Turing e segnala eventuali errori commessi. Questa guida operativa descrive tutti i passi necessari per la definizione e le azioni svolte dagli elementi dell'interfaccia grafica.
La Macchina di Turing
- Che cosa è
- Come è fatta
- Come funziona
- Un esempio
La Macchina di Turing
Prof. Alberto Cimaroli
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:
- 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.
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 e 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
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.
Guida operativa MdT5JFx
La Tastiera
Si possono utilizzare tutti i caratteri minuscoli, maiuscoli, speciali e la barra spaziatrice della tastiera alfanumerica, le cifre dei numeri e gli operatori aritmetici del tastierino numerico;
Tab oppure Enter per terminare l'immissione dei campi richiesti;
Canc per eliminare il carattere dopo il cursore;
Backspace per eliminare il carattere prima del cursore.
Inizializzazione del simulatore
- Fare Click sul bottone START per inizializzare il simulatore
Proseguire scegliendo dal menu File uno dei seguenti punti:
- Nuova MdT... – Definizione nuova Macchina di Turing
- Apri MdT... – Apertura Macchina di Turing precedentemente salvata
- Apri Esempi MdT... – Apertura Esempi di Macchine di Turing
- Apri File .mdt... – Apertura Macchina di Turing salvata nel formato .mdt
Simulatore Multimediale MdT5JFx
Definizione nuova MdT
- Dal menu File selezionare Nuova MdT...
- Inserire l'insieme dei simboli dell'alfabeto separati da una virgola
- il simbolo Blank viene aggiunto in automatico ai simboli immessi
- Inserire l'insieme degli stati separati da una virgola
- al termine dell'immissione, automaticamente, viene assunto come stato iniziale il primo della lista e come stato finale l'ultimo della lista
- Inserire l'insieme delle regole utilizzando l'editor delle quintuple
- per ogni quintupla vengono richiesti stato attuale (appartenente all'insieme degli stati), ingresso (appartenente ai simboli dell'alfabeto oppure Blank indicato dal carattere Space della barra spaziatrice o dal carattere '_' con cui viene rappresentato), stato successivo (appartenente all'insieme degli stati), uscita (appartenente ai simboli dell'alfabeto oppure Blank indicato dal carattere Space della barra spaziatrice o dal carattere '_' con cui viene rappresentato), movimento testina (caratteri 'd' = destra, 's' = sinistra, '_' = nessun movimento)
- a fine immissione il bottone OK accetta la quintupla, la numera e la visualizza
- l'editor permette l'inserimento, la modifica e la cancellazione delle quintuple e dei commenti
Terminata la definizione della MdT il simulatore è pronto per accettare i simboli di ingresso sul nastro e i comandi per l'esecuzione:
- ? Quintupla individua e seleziona, in base allo stato interno e al simbolo sotto la posizione della testina, la quintupla da eseguire
- Esegui Quin. per l'esecuzione della quintupla selezionata
- Esegui Step per l'esecuzione delle quintuple step by step
- Run per l'esecuzione di tutte le quintuple
- l'esecuzione può essere interrotta con il bottone Stop Run
Durante l'esecuzione il simulatore multimediale visualizza il comportamento della Macchina di Turing evidenziando la quintupla in esecuzione, modificando lo stato interno, scrivendo i simboli sul nastro e spostando la posizione della testina.
Apertura MdT
Scegliere il file tipo .mdtj da aprire:
- vengono caricati i simboli dell'alfabeto, l'insieme degli stati e le quintuple; vengono visualizzati lo stato iniziale, lo stato finale, lo stato interno e la descrizione della Macchina di Turing
Terminata l'apertura il simulatore è pronto per accettare i simboli di ingresso sul nastro e i comandi per l'esecuzione.
Apertura Esempio
Scegliere l'esempio da aprire:
- vengono caricati i simboli dell'alfabeto, l'insieme degli stati e le quintuple; vengono visualizzati lo stato iniziale, lo stato finale, lo stato interno e la descrizione della Macchina di Turing
Terminata l'apertura il simulatore è pronto per accettare i simboli di ingresso sul nastro e i comandi per l'esecuzione.
Apertura File .mdt
Scegliere il file tipo .mdt da aprire (formato precedente versione MdT51)
- vengono caricati i simboli dell'alfabeto, l'insieme degli stati e le quintuple; vengono visualizzati lo stato iniziale, lo stato finale, lo stato interno e la descrizione della Macchina di Turing
Terminata l'apertura il simulatore è pronto per accettare i simboli di ingresso sul nastro e i comandi per l'esecuzione.
(*) Il file potrà essere salvato nel nuovo formato .mdtj.
Modello multimediale
Il modello multimediale può essere gestito con i seguenti comandi:
- Dx --> sposta la testina di una posizione verso destra
- <-- Sx sposta la testina di una posizione verso sinistra
- Inizio nastro sposta la testina nella posizione centrale del nastro
- Cancella nastro cancella il contenuto del nastro e sposta la testina nella posizione centrale
- Click su stato interno ripristina lo stato iniziale
- Regolazione velocità
- Regolazione volume audio
Simulatore Multimediale MdT5JFx in esecuzione
Altre funzioni dei Menu File/Edit/Help
Menu File:
- Salva – salva le modifiche intercorse dall'ultimo salvataggio
- Salva con nome... – per salvare in un nuovo file
- Stampa... – stampa la MdT corrente in formato PDF
- Chiudi – chiude l'applicazione
Esempio di stampa MdT in formato PDF
Menu Edit:
- Visualizza Descrizione MdT – visualizza la descrizione della MdT
- Immissione/Modifica Descrizione – per immettere oppure modificare la descrizione della MdT
- Modifica colore sfondo – per modificare il colore di sfondo del simulatore
Menu Help:
- About – visualizza i dati di Copyright
- MdT5JFx on line – per accedere alle pagine Internet del progetto:
- Sito Web principale
- Storia del Progetto
- Guida operativa