Università degli Studi di Milano	Polo Didattico e di Ricerca di Crema	Dipartimento di Tecnologie dell'Informazione
Home page	Teaching page

Secondo laboratorio (9 ottobre 2008)

Si tratta di realizzare un simulatore di Macchina di Turing Universale. Gli scopi di questo laboratorio sono:

seguire passo passo il funzionamento della macchina di Turing per capirlo a fondo
capire il concetto di codifica di una macchina in una stringa di simboli
capire il concetto di simulazione di una macchina su un'altra macchina (sia di una macchina di Turing specifica su una macchina di Turing universale sia di una macchina di Turing universale su un calcolatore programmato in C)
dotarsi di uno strumento col quale esercitarsi a progettare semplici macchine di Turing per l'esame

Descrizione del problema (file PDF da 20KB)
Esempio di input:
Prima approssimazione: struttura generale del programma e definizione delle strutture dati
Seconda approssimazione: interpretazione della linea di comando, caricamento della macchina di Turing codificata e sua deallocazione
Terza approssimazione: controlli di correttezza sul formato della macchina di Turing
Quarta approssimazione: caricamento dell'istanza con controlli di correttezza sul formato e restituzione della soluzione e del contenuto del nastro
Quinta approssimazione: schema generale del funzionamento della macchina (senza implementare ricerca ed esecuzione della transizione)
Sesta approssimazione: ricerca ed esecuzione della transizione
Altro esempio di input:

Pagina aggiornata il