Ranked #1
L21: NP-completeness
L21: NP-completeness
Formal definition of NP-completeness and polynomial-time reductions to prove additional languages are NP-complete once o... Read more
1 Dec 2011
•
1hr 12mins
Ranked #2
L11: Church-Turing thesis and examples of decidable languages
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 ... Read more
1 Nov 2011
•
1hr 18mins
Ranked #3
L12: Universal Turing Machines; The Halting Problem is Recognizable but not Decidable
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 ... Read more
3 Nov 2011
•
1hr 19mins
Ranked #4
L17: Using reductions to prove language undecidable
L17: Using reductions to prove language undecidable
Proving additional languages are not decidable, by using reductions.
15 Nov 2011
•
53mins
Most Popular Podcasts
The Joe Rogan Experience
TED Talks Daily
The Tim Ferriss Show
The Daily
Stuff You Should Know
Oprah's SuperSoul Conversations
Armchair Expert with Dax Shepard
Ranked #5
L9: More TM design and introduction to non-determinstic 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-ta... Read more
20 Oct 2011
•
1hr 19mins
Ranked #6
L8: Introduction to Turing Machines and Computations
L8: Introduction to Turing Machines and Computations
Turing Machines and computations. Recognizable and decidable languages. Examples of designing Turing machines to recogni... Read more
18 Oct 2011
•
1hr 14mins
Ranked #7
L6: The Pumping Lemma, and introduction to CFLs
L6: The Pumping Lemma, and introduction to CFLs
A formal treatment of the pumping lemma for regular languages, and its use in proving that certain languages are not reg... Read more
11 Oct 2011
•
1hr 16mins
Ranked #8
L4: Regular Expressions
L4: Regular Expressions
Introduction to Regular Expressions: Formal recursive definition of a regular expression; composition rules for regular ... Read more
4 Oct 2011
•
1hr 18mins
Ranked #9
Second Lecture on Godel's Incompleteness Theorem
Second Lecture on Godel's Incompleteness Theorem
Completion of the lecture on Godel's first incompleteness theorem.
2 May 2014
•
15mins
Ranked #10
Godel for Goldilocks: 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 fun... Read more
1 May 2014
•
1hr 11mins
