Theory of Computation Videos
Harry H. Porter III, Ph.D.
Created: May, 2014
Prerequisite Knowledge
Background: What You Probably Know (47 mins)
Regular Languages and Finite State Machines
Finite State Machines: Introduction (19 mins)
Finite State Machines: Examples (30 mins)
Operations on Regular Languages (19 mins)
Nondeterministic Finite State Machines: Intro (21 mins)
Nondeterministic Finite State Machines: Formal Definition (15 mins)
Equivalence of Deterministic and Nondeterministic FSMs (23 mins)
Closure of the Regular Operations (13 mins)
Regular Expressions (22 mins)
Equivalence of Regular Expressions and Regular Languages (39 mins)
Pumping Lemma (for Regular Languages) (33 mins)
Regular Languages: Summary (7 mins)
Context Free Grammars and Languages
Intro to Context Free Grammars and Languages (19 mins)
Context Free Grammar Example (8 mins)
Kinds of Context Free Languages (16 mins)
Facts About Context Free Languages (16 mins)
Chomsky Normal Form (16 mins)
Chomsky Hierarchy and Context Sensitive Languages (13 mins)
The Pumping Lemma for CFLs (42 mins)
PDAs: Pushdown Automata (19 mins)
Equivalence of CGFs and PDAs (part 1) (18 mins)
Equivalence of CGFs and PDAs (part 2) (27 mins)
Turing Machines
Introduction to Turing Machines (14 mins)
Turing Machine Examples (12 mins)
Definition of TMs and Related Language Classes (15 mins)
The Church-Turing Thesis (12 mins)
Turing Machine Programming Techniques (19 mins)
Multitape Turing Machines (9 mins)
Nondeterminism in Turing Machines (29 mins)
Turing Machines as Problem Solvers (15 mins)
Enumerators (13 mins)
Decidability and Turing-Recognizability
Decidability and Decidable Problems (32 mins)
More Decidable Problems For DFAs (14 mins)
Problems Concerning Context-Free Languages (20 mins)
The Universal Turing Machine (12 mins)
Infinity: Countable and Uncountable (22 mins)
Languages That Are Not Turing Recognizable (15 mins)
The Undecidability of the Halting Problem (11 mins)
A Language that is Not Turing Recognizable (10 mins)
Reduction: A Technique for Proving Undecidability
Reducibility: A Technique for Proving Undecidability (9 mins)
Halting Problem: A Proof by Reduction (10 mins)
Does a TM Accept Any String? (10 mins)
Computable Functions (2 mins)
The Equivalence of Turing Machines (17 mins)
Reducing One Language to Another (6 mins)
The Post Correspondence Problem (11 mins)
Undecidability of the PCP (32 mins)
Linear Bounded Automata (15 mins)
The Recursion Theorem
A Program That Prints Itself (22 mins)
A Turing Machine That Writes a Description of Itself (14 mins)
The Recursion Theorem (6 mins)
Results from the Recursion Theorem (10 mins)
The Fixed Point Theorem (7 mins)
First-Order Predicate Logic and Gödel's Incompleteness Theorem
First-Order Predicate Logic: An Overview (24 mins)
Truth, Meaning, and Proof (14 mins)
True Statements and Provable Statements (12 mins)
Gödel's Incompleteness Theorem (14 mins)
Time Complexity Classes: P and NP
Time Complexity and Big-O Notation (23 mins)
Computing an Algorithm's Runtime (16 mins)
Time Complexity with Different Computation Models (12 mins)
The Complexity Classes P and NP (12 mins)
Definition of NP and Polynomial Verifiability (32 mins)
NP-Completeness (11 mins)
Proof that SAT is NP-Complete (47 mins)
Space Complexity Classes (14 mins)
Info about video formatting:
Produced on a Mac; H.264; Millions; AAC; 2 channels; 32000 Hz; FPS: 11.99.
Some: 320 x 240; Data rate: about 200 kbit/s
Others: 640 x 360; Data rate: about 330 kbit/s
Problems / Comments on This Web Page