Computation Theory
18 videos
An undergraduate course in the Theory of Computation, taken from first principles to the limits of what a machine can decide. We start with the tools: propositional and predicate logic, set theory and functions, and enough graph theory to work with machines as diagrams. Then the hierarchy, in order — finite automata, nondeterministic finite automata, and regular expressions, with the pumping lemma to prove a language is not regular; right linear grammars, context-free grammars, and pushdown automata, with a second pumping lemma for the languages that are not context-free. The last third is Turing machines and their variants, the Church-Turing thesis and what it means to define "algorithm" at all, decidable and undecidable languages, and reducibility — ending with proofs that particular problems cannot be solved by any machine whatsoever. No prior computer science is assumed. The logic and set theory you need are built in the opening lectures.
Resources
- 1
Lecture 1 (Computation Theory) Propositional and Predicate Logic
2:17:05
- 2
Lecture 2 (Computation Theory) Set Theory and Functions
1:56:34
- 3
Lecture 3 (Computation Theory) Graph Theory and Finite Automata
2:02:13
- 4
Lecture 4 (Computation Theory) Finite Automata
2:10:07
- 5
Lecture 5 (Computation Theory) Nondeterministic Finite Automata
2:10:20
- 6
Lecture 6 (Computation Theory) Nondeterministic Finite Automata and Regular Expressions
1:48:08
- 7
Lecture 7 (Computation Theory) Regular Expressions and the Pumping Lemma
2:02:30
- 8
Lecture 8 (Computation Theory) Pumping Lemma, Right Linear Grammars, and Context-Free Grammars
1:50:09
- 9
Lecture 9 (Computation Theory) Context-Free Grammars and Pushdown Automata
2:01:16
- 10
Lecture 10 (Computation Theory) Pushdown Automata, Non-Context-Free Languages, and Pumping Lemma 2.0
1:43:22
- 11
Lecture 11 (Computation Theory) Pumping Lemma, Non-Context-Free Languages, and Review
1:31:41
- 12
Lecture 12 (Computation Theory) Turing Machines
1:15:14
- 13
Lecture 13 (Computation Theory) Turing Machine Variants
1:40:34
- 14
Lecture 14 (Computation Theory) Church-Turing Thesis and the Definition of an Algorithm
1:03:54
- 15
Lecture 15 (Computation Theory) Decidable and Undecidable Languages
1:51:13
- 16
Lecture 16 (Computation Theory) Decidability and Undecidability
1:47:44
- 17
Lecture 17 (Computation Theory) Reducibility and Undecidable Problems
1:58:47
- 18
Lecture 18 (Computation Theory) Undecidable Problems and Mapping Reducibility
1:27:41