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: Turing machine enhancements, decidability vs. recognizability, recognition and enumeration, halting problem language is recognizable but not decidable, decidability and lexicographic-order enumerability, building an enumerator from a recognizer, building a recognizer from an enumerator, dovetailing enumeration, avoiding duplicates, parallel enumeration, Chomsky hierarchy, why is it difficult to decide / recognize. sums-of-three-cubes, Diaphantine equations, Hilbert's Tenth Problem, closure properties of decidable and recognizable languages