# click the up-left corner to select videos from the playlist
source: UC Davis Academics 2014年10月17日
This is a rigorous undergraduate course on the Theory of Computation, using the classic text "Introduction to the Theory of Computation" by Michael Sipser. The course covers machine models and languages defined by Finite State Machines, Context-Free Languages, and Turing Machines.
There are four major theorems (and their uses) that we will study during this course, providing complete proofs: the pumping Lemma for regular languages, used to show that there are languages that are not regular; the existence of a Universal Turing Machine; undecidability of the Halting problem; and Cook's theorem that NP-complete problems exist. In addition to these major results, and other results, a central goal of the course is to increase student's skill level in understanding and writing rigorous mathematical proofs.
L1: Introduction to Finite-state Machines, Regular Languages 1:05:58
L2: Regular Languages and non-deterministic FSMs 1:20:57
L4: Regular Expressions 1:18:33
L5: Regular expressions, regular languages, and non-regular languages 1:17:52
L6: The Pumping Lemma, and introduction to CFLs 1:16:42
L7: Contex-Free Grammars and Push-Down Automata 1:18:38
L8: Introduction to Turing Machines and Computations 1:14:56
L9: More TM design and introduction to non-determinstic TMs 1:19:38
L10: Equivalence of non-deterministic and deterministic TMs 1:16:05
L11: Church-Turing thesis and examples of decidable languages 1:18:05
L12: Universal Turing Machines; The Halting Problem is Recognizable but not Decidable 1:19:07
L13: Diagonalization, countability and uncountability 1:13:16
L14: More Diagonalization; Proof that Turing machines are countable 11:11
L15: Proof by diagonalization that ATM (Halting problem) is not decidable 24:49
L16: Unrecognizable languages, and reductions 40:08
L17: Using reductions to prove language undecidable 53:51
L18: More complex reductions 1:14:50
L19: Uncomputable functions, and introduction to complexity 1:21:10
L20: P, NP and polynomial-time reductions 32:47
L21: NP-completeness 1:12:31
L22: A more informal introduction to NP-completeness, Supplemental Lecture 1 48:03
L23: NP Completeness, Supplemental lecture 2 45:30
L24: NP Completeness, Supplemental lecture 3 50:27
L25: Minimizing Finite State Machines 1:13:43
L26: Minimizing the number of states in a DFA 1:25:54
Godel for Goldilocks: Godel's First Incompleteness Theorem 37:56
Second Lecture on Godel's Incompleteness Theorem 33:46
