Uploaded March 2018 | Updated September 2026, 15 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: Chomsky hierarchy reloaded, resource-bounded computation, time / space / other resources, the dramatic difference between disk & RAM speeds, complexity classes, deterministic vs. non-deterministic time & space, time is tape-dependent, space is tape-independent, 1-tape simulation of k-tapes, 0^n1^n is in DTIME(n^2) / DSPACE(n) / DTIME(n log n) for 1-tape TMs, 0^n1^n is in DTIME(n) and DSPACE(log n) for 2-tape TMs
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: Chomsky hierarchy reloaded, resource-bounded computation, time / space / other resources, the dramatic difference between disk & RAM speeds, complexity classes, deterministic vs. non-deterministic time & space, time is tape-dependent, space is tape-independent, 1-tape simulation of k-tapes, 0^n1^n is in DTIME(n^2) / DSPACE(n) / DTIME(n log n) for 1-tape TMs, 0^n1^n is in DTIME(n) and DSPACE(log n) for 2-tape TMs
