Uploaded March 2018 | Updated September 2026, 7 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: type errors revisited, reducibilities, examples of reductions, properties of recognizable languages, uncountability of the properties, the two trivial properties, Rice's theorem, corollaries and misapplications of Rice's theorem, negative results, Streisand Effect, Chomsky hierarchy revisited, closure properties of decidable and recognizable languages