# Material for the theory of computation class taught by Emanuele "Manu" Viola.

## 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.

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.

# Units

The next main file groups the video lectures in units, and gives corresponding exercises: toc-units

# Video lectures

All videos are also available on Manu's YouTube channel.

### Video 1

Introduction to the class
[MS 1.1], [Si 0.1, 0.4]

### Video 2

Introduction to DFA
[E 3.1], [MS 2.2], [Sa 1.4.2], [Si 1.1]

### Video 3

Formal definition of DFA
[E 3.2], [MS 2.2], [Sa 3.1, 4.1], [Si 1.1]

### Video 4

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]

### Video 5

NFA
[Sa 3.1.5, 4.1] [MS 2.4, 2.4.4] [E 4.1] [Si 1.2]

### Video 6

Equivalence of NFA and DFA
[Sa 4.2] [MS 2.5] [Si 1.2]

### Video 7

Finish closure properties
[MS 2.6, 2.4.4] [Si 1.2]

### Video 8

Regular expressions, equivalence with NFA
[Sa 4.3, 4.4] [MS 2.7, 2.8, 2.8.2] [Si 1.3] [E 2.3]

### Video 9

Non-regular languages, pumping lemma
[Sa 4.5] [MS 2.9, 2.9.1] [E 3.8] [Si 1.4]

### Video 10

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]

### Video 12

Closure properties, pushdown automata
[Sa 4.8, 4.13.2] [MS 3.5, 3.6, 3.7] [Si 2.2]

### Video 13

Non-context free languages, pumping lemma
[Sa 4.13.1] [MS 3.8, 3.8.2] [E 5.6] [Si 2.3]

### Video 14

A grammar for the language of strings with the same number of a and b
[MS 1.3.6]

### Video 15

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]

### Video 16

An undecidable language
[Sa 5.7.2, 5.7.3] [MS 1.3.4, 5.1.4, 5.1.5] [Si 4.2]

### Video 17

Undecidable languages via reductions
[Sa 5.8] [MS 6.5.1] [Si 5.1]

### Video 18

Complexity theory
[Sa 8.5] [MS 6.2, 6.3] [Si 7.1, 7.2, 7.3]

### Video 19

3Sat reduces to Clique
[Sa 8.2] [MS 6.5.1] [Si 7.4] [V 4.3.1]

### Video 20

Clique reduces to cover-by-vertexes
[Si 7.4] [V 4.3.2]

### Video 21

3Sat reduces to subset-sum
[Si 7.4] [V 4.3.3]

### Video 22

3Sat reduces to 3Color
[V 4.3.4]

### Video 23

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

### Video 24

Exponential time
[Sa 8.5.2] [MS 6.3.2] [Si 7.3]

### Video 25

A language not in P
[Si 9.1]

### Video 26

Proof of Cook-Levin theorem
[Si 7.5] [E 9.6]