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: Turing machine "enhancements", larger alphabets, double-sided infinite tapes, multiple heads, multiple tapes, higher-dimensional tapes, non-determinism, combinations of enhancements, commutativity of compositions, equivalent TMs and programs, recognizability vs. decidability vs. enumerability, decidability and lexicographic orders, recognizability and enumerability, parallel simulation, non-response vs. explicit no, "simple" examples of recognizable non-decidable sets