Theory of Computation - Fall 2011: Recent Episodes
Dan Gusfield
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.
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.
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.
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.
This is a supplemental lecture Introducing the concept of NP through reductions. It was given in another course, but since the treatment of NP completeness was so compressed in Fall 2011, I think this lecture, and two more, will be quite valuable.
Formal definition of NP-completeness and polynomial-time reductions to prove additional languages are NP-complete once one NP-complete language has been established.
Proof by diagonalization that there are uncomputable functions; introduction to complexity theory, big-Oh notation, definition of worst-case for a non-deterministic. Turing machine; definition of the classes P and NP.
Proof that there are languages which are not even recognizable. Introduction to reductions.
More on diagonalization in preparation for proving, by diagonalization, that ATM is not decidable. Proof that the set of all Turing Machines is countable.
Review of the undecidable language ATM, the Halting Problem; introduction to diagonalization and countability; proof by diagonalization that the real numbers are not countable.
Introduction to language ATM, the halting problem; Universal Turing machines show that ATM is recognizable. UTMs define what a computer is in the way that TMs define what algorithms are. Proof that ATM is not decidable by a self-reference argument. This lecture is one of the highlights of the course, showing one of the high points of deduction in the twentieth century.
Church-Turing thesis; examples of decidable languages. An algorithm is defined by the existence of a TM that implements the algorithm. One of Turing's great contributions is in formally defining what an algorithm is.
More examples of designing Turing Machines to recognize and decide languages. Equivalence of Multi-tape TMs to single-tape TMs. Introduction to Non-deterministic Turing Machines.
Turing Machines and computations. Recognizable and decidable languages. Examples of designing Turing machines to recognize or decide particular languages.
Review of CFLs and grammars; overview of basic results of CFLs without proofs. Introduction to push-down automata (PDA). Statement of the equivalence of CFLs and DPAs.
A formal treatment of the pumping lemma for regular languages, and its use in proving that certain languages are not regular. Introduction to context free languages and grammars.
Completion of equivalence of regular languages and regular expressions. Introduction to the proof that there are languages that are not regular; first an ad hoc proof using the essence of the pumping lemma, but without formally stating it.
Introduction to Regular Expressions: Formal recursive definition of a regular expression; composition rules for regular expressions; operators on regular expressions; start of proof of the equivalence of regular expressions and regular languages.
Operations on regular languages, union and concatenation. Introduction to non-deterministic finite state machines.