Podcasts Technology Theory of Computation - Fall 2011
Theory of Computation - Fall 2011

Theory of Computation - Fall 2011

27 episodes

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.

Podcasts

Second Lecture on Godel's Incompleteness Theorem

Published: May 2, 2014, 7 a.m.
Duration: 15 minutes 58 seconds

Listed in: Technology

Godel for Goldilocks: Godel's First Incompleteness Theorem

Published: May 1, 2014, 7 a.m.
Duration: 1 hour 11 minutes

Listed in: Technology

L26: Minimizing the number of states in a DFA

Published: Feb. 10, 2012, 8 a.m.
Duration: 1 hour 25 minutes 53 seconds

Listed in: Technology

L25: Minimizing Finite State Machines

Published: Jan. 27, 2012, 8 a.m.
Duration: 1 hour 13 minutes 42 seconds

Listed in: Technology

L24: NP Completeness, Supplemental lecture 3

Published: Dec. 13, 2011, 8 a.m.
Duration: 50 minutes 25 seconds

Listed in: Technology

L23: NP Completeness, Supplemental lecture 2

Published: Dec. 9, 2011, 8 a.m.
Duration: 45 minutes 29 seconds

Listed in: Technology

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

Published: Dec. 3, 2011, 8 a.m.
Duration: 48 minutes 2 seconds

Listed in: Technology

L21: NP-completeness

Published: Dec. 1, 2011, 8 a.m.
Duration: 1 hour 12 minutes 30 seconds

Listed in: Technology

L20: P, NP and polynomial-time reductions

Published: Nov. 29, 2011, 8 a.m.
Duration: 32 minutes 46 seconds

Listed in: Technology

L19: Uncomputable functions, and introduction to complexity

Published: Nov. 22, 2011, 8 a.m.
Duration: 1 hour 21 minutes 10 seconds

Listed in: Technology

L18: More complex reductions

Published: Nov. 17, 2011, 8 a.m.
Duration: 1 hour 14 minutes 49 seconds

Listed in: Technology

L17: Using reductions to prove language undecidable

Published: Nov. 15, 2011, 8 a.m.
Duration: 53 minutes 50 seconds

Listed in: Technology

L16: Unrecognizable languages, and reductions

Published: Nov. 12, 2011, 8 a.m.
Duration: 40 minutes 12 seconds

Listed in: Technology

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

Published: Nov. 11, 2011, 8 a.m.
Duration: 24 minutes 52 seconds

Listed in: Technology

L14: More Diagonalization; Proof that Turing machines are countable

Published: Nov. 10, 2011, 8 a.m.
Duration: 11 minutes 10 seconds

Listed in: Technology

L13: Diagonalization, countability and uncountability

Published: Nov. 8, 2011, 8 a.m.
Duration: 1 hour 13 minutes 15 seconds

Listed in: Technology

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

Published: Nov. 3, 2011, 7 a.m.
Duration: 1 hour 19 minutes 6 seconds

Listed in: Technology

L11: Church-Turing thesis and examples of decidable languages

Published: Nov. 1, 2011, 7 a.m.
Duration: 1 hour 18 minutes 4 seconds

Listed in: Technology

L10: Equivalence of non-deterministic and deterministic TMs

Published: Oct. 25, 2011, 7 a.m.
Duration: 1 hour 16 minutes 4 seconds

Listed in: Technology

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

Published: Oct. 20, 2011, 7 a.m.
Duration: 1 hour 19 minutes 37 seconds

Listed in: Technology

L8: Introduction to Turing Machines and Computations

Published: Oct. 18, 2011, 7 a.m.
Duration: 1 hour 14 minutes 55 seconds

Listed in: Technology

L7: Contex-Free Grammars and Push-Down Automata

Published: Oct. 13, 2011, 7 a.m.
Duration: 1 hour 18 minutes 37 seconds

Listed in: Technology

L6: The Pumping Lemma, and introduction to CFLs

Published: Oct. 11, 2011, 7 a.m.
Duration: 1 hour 16 minutes 41 seconds

Listed in: Technology

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

Published: Oct. 6, 2011, 7 a.m.
Duration: 1 hour 17 minutes 51 seconds

Listed in: Technology

L4: Regular Expressions

Published: Oct. 4, 2011, 7 a.m.
Duration: 1 hour 18 minutes 32 seconds

Listed in: Technology

L2: Regular Languages and non-deterministic FSMs

Published: Sept. 27, 2011, 7 a.m.
Duration: 1 hour 20 minutes 56 seconds

Listed in: Technology

L1: Introduction to Finite-state Machines, Regular Languages

Published: Sept. 22, 2011, 7 a.m.
Duration: 1 hour 6 minutes 21 seconds

Listed in: Technology