Fondamenti di Informatica – Cattolica Brescia

• Frequentanti: materiale fornito dal docente
• Non frequentanti: Tanenbaum, “Architettura dei calcolatori. Un approccio strutturale” capitoli 2, 3 e 4.1 (primo paragrafo del capitolo 4)

Argomenti del programma: Teoria della computabilità: Funzioni parziali e algoritmi. La diagonalizzazione e il problema dell’halt. Sintassi dei programmi while. Teoria elementare della computazione. Metodologia dei programmi. Il teorema di ricorsione e le proprietà delle enumerazioni. Computabilità di insiemi: il teorema di incompletezza di Gödel e il teorema di Rice. Macchine di Turing.