CS-C2160 - Theory of Computation, 12.01.2021-14.04.2021
This course space end date is set to 14.04.2021 Search Courses: CS-C2160
10. More on undecidability
Krav för slutförande
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.