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.