Material for the theory of computation class taught by Emanuele "Manu" Viola.
Video lectures below
Description
Introduces the theory behind computers and computing aimed at answering the question, “What are the capabilities and limitations of computers?” Covers automata theory, computability, and complexity. The automata theory portion includes finite automata, regular expressions, nondeterminism, nonregular languages, context-free languages, pushdown automata, and noncontext-free languages. The computability portion includes Turing machines, the Church-Turing thesis, decidable languages, and the Halting theorem. The complexity portion includes the classes P and NP, the P vs. NP question, and NP-completeness.
Additional references
We will be following the video lectures below. The video lectures are in turn based on Manu's slides.
No textbook is required. However, as optional readings, below we accompany the list of videos with pointers to overlapping material from the following books:
- [E] Models of Computation, by Erickson. Link.
- [MS] Introduction to Theory of Computation, by Maheshwari and Smid. Link.
- [Sa] Models of Computation, by Savage. Link.
- [Si] Introduction to the Theory of Computation, by Sipser.
- [V] Mathematics of the Impossible, by Viola. Link.
The next main file groups the video lectures in units, and gives corresponding exercises:
toc-units
All videos are also available on Manu's YouTube channel.
Introduction to the class
[MS 1.1], [Si 0.1, 0.4]
Introduction to DFA
[E 3.1], [MS 2.2], [Sa 1.4.2], [Si 1.1]
Formal definition of DFA
[E 3.2], [MS 2.2], [Sa 3.1, 4.1], [Si 1.1]
Closure under complementation and union. What is a proof?
[Sa 1.3, 4.6]
[MS 2.6, 3.2.3]
[Si 0.4, 1.1]
NFA
[Sa 3.1.5, 4.1]
[MS 2.4, 2.4.4]
[E 4.1]
[Si 1.2]
Equivalence of NFA and DFA
[Sa 4.2]
[MS 2.5]
[Si 1.2]
Finish closure properties
[MS 2.6, 2.4.4]
[Si 1.2]
Regular expressions, equivalence with NFA
[Sa 4.3, 4.4]
[MS 2.7, 2.8, 2.8.2]
[Si 1.3]
[E 2.3]
Non-regular languages, pumping lemma
[Sa 4.5]
[MS 2.9, 2.9.1]
[E 3.8]
[Si 1.4]
Context-free languages, grammars
[Sa 4.9.3, 4.9.4]
[MS 3.1, 3.2]
[E 5.1]
[Si 2.1]
Ambiguity
[Si 2.1]
Closure properties, pushdown automata
[Sa 4.8, 4.13.2]
[MS 3.5, 3.6, 3.7]
[Si 2.2]
Non-context free languages, pumping lemma
[Sa 4.13.1]
[MS 3.8, 3.8.2]
[E 5.6]
[Si 2.3]
A grammar for the language of strings with the same number of a and b
[MS 1.3.6]
Turing machines, decidable languages, Church-Turing thesis, locality
[Sa 5.1, 5.2, 5.4, 5.7.1]
[MS 4.1, 4.2, 4.4, 5.1, 5.1.1, 5.1.2, 5.1.3]
[E 6.2, 6.3]
[Si 3.1, 4.1]
An undecidable language
[Sa 5.7.2, 5.7.3]
[MS 1.3.4, 5.1.4, 5.1.5]
[Si 4.2]
Undecidable languages via reductions
[Sa 5.8]
[MS 6.5.1]
[Si 5.1]
Complexity theory
[Sa 8.5]
[MS 6.2, 6.3]
[Si 7.1, 7.2, 7.3]
3Sat reduces to Clique
[Sa 8.2]
[MS 6.5.1]
[Si 7.4]
[V 4.3.1]
Clique reduces to cover-by-vertexes
[Si 7.4]
[V 4.3.2]
3Sat reduces to subset-sum
[Si 7.4]
[V 4.3.3]
3Sat reduces to 3Color
[V 4.3.4]
NP completeness
[Sa 8.7, 8.8, 8.10]
[MS 6.5.2, 6.5.3, 6.5.4]
[Si 7.4, 7.5]
Supermario is hard, a cool video: https://www.youtube.com/watch?v=oS8m9fSk-Wk
Exponential time
[Sa 8.5.2]
[MS 6.3.2]
[Si 7.3]
A language not in P
[Si 9.1]
Proof of Cook-Levin theorem
[Si 7.5]
[E 9.6]