Podcasts Technology Theory of Computation - Fall 2011

Theory of Computation - Fall 2011

27 episodes

None

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