Theory of Computation - Fall 2011

Completion of the lecture on 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.

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.

Supplemental lecture 3 on less formal treatment of NP-completeness.

A second supplemental lecture on a more informal treatment of NP-completeness.

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.

P, NP, and polynomial-time reductions. Is P = NP?

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.

More reductions to prove that additional problems are undecidable.

Proving additional languages are not decidable, by using reductions.

Proof that there are languages which are not even recognizable. Introduction to reductions.

Proof, by diagonalization, that ATM, the Halting Problem, is not decidable.

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.

Detailed proof of the equivalence of non-determinisitc TMs and deterministic TMs.

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.

This introduction covers deterministic finite-state machines and regular languages.