Theory of Computation - Fall 2011 Dan Gusfield
-
- Technology
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.
-
- video
Second Lecture on Godel's Incompleteness Theorem
Completion of the lecture on Godel's first incompleteness theorem.
-
- video
Godel for Goldilocks: Godel's First Incompleteness Theorem
Godel's first incompleteness theorem, requiring minimal background. You only need to know what an integer is, what a function is and that a computer program is a finite series of statements written in some finite alphabet.
-
- video
L26: Minimizing the number of states in a DFA
Completion of the method to minimize the number of states in a DFA for any regular language. A by-product is a proof that the minimizing DFA is unique for any given regular language.
-
- video
L25: Minimizing Finite State Machines
In this supplemental lecture we define what is meant by a minimized DFA, and introduce an efficient algorithm to minimize the number of states in a DFA for any regular language.
-
- video
L24: NP Completeness, Supplemental lecture 3
Supplemental lecture 3 on less formal treatment of NP-completeness.
-
- video
L23: NP Completeness, Supplemental lecture 2
A second supplemental lecture on a more informal treatment of NP-completeness.