# Theory of Computation - Fall 2011

## About this podcast

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.

The podcast Theory of Computation - Fall 2011 is embedded on this page from an open RSS feed. All files, descriptions, artwork and other metadata from the RSS-feed is the property of the podcast owner and not affiliated with or validated by Podplay.

## About this podcast

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.

The podcast Theory of Computation - Fall 2011 is embedded on this page from an open RSS feed. All files, descriptions, artwork and other metadata from the RSS-feed is the property of the podcast owner and not affiliated with or validated by Podplay.

# Theory of Computation - Fall 2011

## Episodes

- 2014
### Second Lecture on Godel's Incompleteness Theorem

Completion of the lecture on Godel's first incompleteness theorem.

### 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.

- 2012
### 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.

### 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.

- 2011
### L24: NP Completeness, Supplemental lecture 3

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

### L23: NP Completeness, Supplemental lecture 2

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

### L22: A more informal introduction to NP-completeness, Supplemental Lecture 1

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.

### L21: NP-completeness

Formal definition of NP-completeness and polynomial-time reductions to prove additional languages are NP-complete once one NP-complete language has been established.

### L19: Uncomputable functions, and introduction to complexity

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.

### L17: Using reductions to prove language undecidable

Proving additional languages are not decidable, by using reductions.

### L16: Unrecognizable languages, and reductions

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

### L15: Proof by diagonalization that ATM (Halting problem) is not decidable

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

### L14: More Diagonalization; Proof that Turing machines are countable

More on diagonalization in preparation for proving, by diagonalization, that ATM is not decidable. Proof that the set of all Turing Machines is countable.

### L13: Diagonalization, countability and uncountability

Review of the undecidable language ATM, the Halting Problem; introduction to diagonalization and countability; proof by diagonalization that the real numbers are not countable.

### L12: Universal Turing Machines; The Halting Problem is Recognizable but not Decidable

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.

### L11: Church-Turing thesis and examples of decidable languages

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.

### L10: Equivalence of non-deterministic and deterministic TMs

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

### L9: More TM design and introduction to non-determinstic 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.