Uploaded March 2018 | Updated September 2026, 9 hours ago

---

This lecture is part of a course on the Theory of Computation, by Professor Gabriel Robins at the University of Virginia (CS3102 Spring 2018), with PowerPoint slides at http://www.cs.virginia.edu/~robins/cs3102 and other related videos at http://www.cs.virginia.edu/~robins/videos.html

Specific topics covered in this lecture: Chomsky hierarchy revisited, closure properties of decidable and recognizable languages, reducibilities / reductions, additional undecidable problems, the halting problem on the empty string, existence vs. knowing the value, the language emptyness problem, the language regularity problem, language properties, undecidability of almost all properties, Rice's theorem