Berekenbaarheidstheorie: reduceerbaarheid (1‪)‬ Berekenbaarheidstheorie

TI2320 (IN2505-II). Berekenbaarheidstheorie. De centrale vraag van dit college is "Welke berekeningen kunnen in principe op een computer worden uitgevoerd?" Deze vraag behoort tot het domein van de berekenbaarheidstheorie. Tijdens het college worden de belangrijke begrippen en technieken uit dit gebied geïntroduceerd: diagonalisatie, Turingmachines, niet-determinisme, opsombaarheid, beslisbaarheid, berekenbaarheid, reductie en recursiestelling.