Gli automi e le macchine di Turing rappresentano modelli di calcolo ideali attraverso i quali definire in maniera comprensibile anche a non esperti molti dei concetti di base dell'informatica: la nozione di algoritmo, la rappresentazione simbolica dei dati, la nozione di computazione e proprietà quali correttezza e efficienza di un programma. Tutti questi concetti combinati con la possibilità di ragionare su programmi come dati portano in maniera naturale alla definizione della frontiera tra problemi risolvibili e non risolvibili con un elaboratore e allo studio dell'espressività di diversi modelli di calcolo. Sorprendentemente le macchine di Turing risultano essere un modello di calcolo universale, cioè in grado di eseguire gli stessi calcoli di un qualsiasi elaboratore. In questo senso la macchina di Turing è il miglior computer possibile. Saremo introdotti ai concetti di base della programmazione e della computazione simbolica attraverso automi e macchine di Turing. Eseguendo esercizi di programmazione su carta o attraverso dei simulatori e rispondendo a quesiti sul modello di computazione, comprenderemo i concetti considerati e gli aspetti legati all'espressività dei linguaggi di programmazione in maniera divertente.

Università degli Studi di Genova - Dipartimento di Informatica Bioingegneria Robotica e Ingegneria dei Sistemi