Theory of Computation - Fall 2011

Follow Theory of Computation - Fall 2011
Share on
Copy link to clipboard

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 m…

Dan Gusfield

  • May 2, 2014 LATEST EPISODE
  • infrequent NEW EPISODES
  • 1h 3m AVG DURATION
  • 27 EPISODES


Search for episodes from Theory of Computation - Fall 2011 with a specific topic:

Latest episodes from Theory of Computation - Fall 2011

Second Lecture on Godel's Incompleteness Theorem

Play Episode Listen Later May 2, 2014 15:58


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

Godel for Goldilocks: Godel's First Incompleteness Theorem

Play Episode Listen Later May 1, 2014 71:00


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.

L26: Minimizing the number of states in a DFA

Play Episode Listen Later Feb 10, 2012 85:53


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

Play Episode Listen Later Jan 27, 2012 73:42


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.

L24: NP Completeness, Supplemental lecture 3

Play Episode Listen Later Dec 13, 2011 50:25


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

L23: NP Completeness, Supplemental lecture 2

Play Episode Listen Later Dec 9, 2011 45:29


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

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

Play Episode Listen Later Dec 3, 2011 48:02


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

Play Episode Listen Later Dec 1, 2011 72:30


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

L20: P, NP and polynomial-time reductions

Play Episode Listen Later Nov 29, 2011 32:46


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

L19: Uncomputable functions, and introduction to complexity

Play Episode Listen Later Nov 22, 2011 81:10


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.

L18: More complex reductions

Play Episode Listen Later Nov 17, 2011 74:49


More reductions to prove that additional problems are undecidable.

L17: Using reductions to prove language undecidable

Play Episode Listen Later Nov 15, 2011 53:50


Proving additional languages are not decidable, by using reductions.

L16: Unrecognizable languages, and reductions

Play Episode Listen Later Nov 12, 2011 40:12


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

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

Play Episode Listen Later Nov 11, 2011 24:52


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

L14: More Diagonalization; Proof that Turing machines are countable

Play Episode Listen Later Nov 10, 2011 11:10


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

Play Episode Listen Later Nov 8, 2011 73:15


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

Play Episode Listen Later Nov 3, 2011 79:06


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

Play Episode Listen Later Nov 1, 2011 78:04


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

Play Episode Listen Later Oct 25, 2011 76:04


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

L9: More TM design and introduction to non-determinstic TMs

Play Episode Listen Later Oct 20, 2011 79:37


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.

L8: Introduction to Turing Machines and Computations

Play Episode Listen Later Oct 18, 2011 74:55


Turing Machines and computations. Recognizable and decidable languages. Examples of designing Turing machines to recognize or decide particular languages.

L7: Contex-Free Grammars and Push-Down Automata

Play Episode Listen Later Oct 13, 2011 78:37


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.

L6: The Pumping Lemma, and introduction to CFLs

Play Episode Listen Later Oct 11, 2011 76:41


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.

L5: Regular expressions, regular languages, and non-regular languages

Play Episode Listen Later Oct 6, 2011 77:51


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.

L4: Regular Expressions

Play Episode Listen Later Oct 4, 2011 78:32


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.

L2: Regular Languages and non-deterministic FSMs

Play Episode Listen Later Sep 27, 2011 80:56


Operations on regular languages, union and concatenation. Introduction to non-deterministic finite state machines.

L1: Introduction to Finite-state Machines, Regular Languages

Play Episode Listen Later Sep 22, 2011 66:21


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

Claim Theory of Computation - Fall 2011

In order to claim this podcast we'll send an email to with a verification link. Simply click the link and you will be able to edit tags, request a refresh, and other features to take control of your podcast page!

Claim Cancel