Formal Languages and Computability (INF3, Autumn'05)
Lecture 11
Main topic:
Reducibility
Lecture Plan
- languages that are not Turing recognizable
- closure properties of decidable and recognizable languages
- reduction in the computability theory
- undecidability of the halting and emptiness problem
for TMs
Reading