Uploaded April 2018 | Updated November 2026, 5 days 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: the course TAs talk about cheating/plagiarism -related issues - please don't cheat!, probabilistic Turing machines, the power of randomness in computation, Bounded-error Probabilistic Polunomial time (BPP), primality testing, BPP and the polynomial hierarchy, pseudorandom number generators, the "Complexity Zoo", the extrended Chomsky hierarchy, the "busy beaver" function, non-halting space-bounded computations, context-sensitive grammars, universality of context-sensitive grammars, Occam's razor
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: the course TAs talk about cheating/plagiarism -related issues - please don't cheat!, probabilistic Turing machines, the power of randomness in computation, Bounded-error Probabilistic Polunomial time (BPP), primality testing, BPP and the polynomial hierarchy, pseudorandom number generators, the "Complexity Zoo", the extrended Chomsky hierarchy, the "busy beaver" function, non-halting space-bounded computations, context-sensitive grammars, universality of context-sensitive grammars, Occam's razor










