CS-C2160 - Theory of Computation, 12.01.2021-14.04.2021
Kurssiasetusten perusteella kurssi on päättynyt 14.04.2021 Etsi kursseja: CS-C2160
10. More on undecidability
Suorituksen vaatimukset
1. Undecidability of some Turing machine properties: the halting and non-emptiness problems.
2. Other undecidability results: logic and algebra, Post's correspondence problem, the Chomsky hierarchy. Computable functions and reductions. Excursion: Post's correspondence problem.