Uploaded February 2018 | Updated September 2026, 36 minutes 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: the Chomsky Hierarchy, regular / context-free / decidable / recognizable languages, Turing machines (TMs), tapes, tape alphabet, TM recognition, power and generality of TMs, TM to recognize 0^n1^n2^n, "marking" the tape, arbitrary complexity arises from interacting simple parts, accepting and rejecting strings, "crossing off" tape characters, "simplicity" and ubiquity of the Turing machine model, TM "enhancements", larger alphabets, double-sided infinite tapes, multiple heads, multiple tapes, two-dimensional tapes, row-major order, compositions
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: the Chomsky Hierarchy, regular / context-free / decidable / recognizable languages, Turing machines (TMs), tapes, tape alphabet, TM recognition, power and generality of TMs, TM to recognize 0^n1^n2^n, "marking" the tape, arbitrary complexity arises from interacting simple parts, accepting and rejecting strings, "crossing off" tape characters, "simplicity" and ubiquity of the Turing machine model, TM "enhancements", larger alphabets, double-sided infinite tapes, multiple heads, multiple tapes, two-dimensional tapes, row-major order, compositions
