Uploaded February 2018 | Updated September 2026, 11 hours ago

---

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

Specific topics covered in this lecture: recognizable vs. decidable, enumeration and lexicographic order, closure properties of decidable and recognizable languages, reducibilities / reductions, the halting problem on the empty string, Rice's theorem, properties, ubiquity of undecidability, the Chomsky hierarchy revisited, proper and non-proper containments, space and time hierarchies