Prof. Miriam Di Ianni

• Dispense a cura del docente disponibili sul sito del corso.
• Il materiale didattico, gli strumenti informatici e il diario delle lezioni aggiornato in tempo reale consentono agli studenti non frequentanti (qualora lo desiderino) di poter avere un riscontro costante con il docente

Argomenti del programma: Introduzione al corso: algoritmi, problemi, modelli di calcolo. Macchine di Turing: trasduttori e riconoscitori, a un nastro e a k nastri, deterministiche e non deterministiche. Macchina di Turing universale. Linguaggi e funzioni. Linguaggi e linguaggi complemento. Accettabilità e decidibilità di linguaggi. Calcolabilità di funzioni. La tesi di Church Turing e modello di calcolo equivalenti alla macchina di Turing.