La computabilità da Leibniz ai giorni nostri. Il concetto di Algoritmo.
Alfabeti, stringhe e linguaggi. Il ruolo che stringhe e linguaggi hanno per rappresentare l’informazione.
Linguaggi. Strumenti per definire un linguaggio. Espressioni Regolari, Approccio Generativo, Approccio Riconoscitivo.
Calcolabilità e Grammatiche. Grammatiche e automi. La gerarchia di Chomsky. Linguaggi regolari, liberi da contesto, dipendenti dal contesto.
Automi di riconoscimento. Deterministici e Non Deterministici. Trasformazioni.
Macchine di Turing. Funzioni calcolabili e linguaggi decidibili secondo Turing. La tesi di Church. Macchine di Turing non deterministiche.
Problemi senza soluzione. La macchina Universale. Il problema dell'arresto. Il decimo problema di Hilbert. I teoremi di Rice e di Kleene.
Funzioni Ricorsive. Calcolabilità secondo Church. Funzioni parziali ricorsive.
Calcolabilità e Linguaggi di Programmazione. Il linguaggio WHILE: sintassi e semantica.