Theory of Computation

Fall 2023

Tuesday 1:30–2:45 p.m.
Thursday 1:30–2:45 p.m.
Sanders Physics 105

Professor Gordon

↓ Current
Tuesday Thursday

Models of computation

Aug. 29

Theory of computation

Aug. 31

Languages and automata

Finite automata

Sep. 5

Deterministic finite automata

Sep. 7

Nondeterministic finite automata

Regular languages and automata

Sep. 12

Relating DFAs and NFAs

Sep. 14

Properties of regular languages

Regular and non-regular languages

Sep. 19

Regular expressions

Sep. 21

The limits of regular languages

Exam 1

Sep. 26

Exam 1 review

Sep. 28

Exam 1

Context-free grammars

Oct. 3

Context-free grammars

Oct. 5

Context-free grammars and context-free languages

Pushdown automata

Oct. 10

Pushdown automata

Oct. 12

The power of PDAs

October Break

Oct. 17

🍁

Oct. 19

🍂

Context-free and non-context-free languages

Oct. 24

The limits of context-free languages

Oct. 26

Parsing with CFGs

Exam 2

Oct. 31

Exam 2 review

Nov. 2

Exam 2

Turing machines

Nov. 7

Turing machines

Nov. 9

Designing Turing machines

Decidable languages

Nov. 14

Turing machines and computation

Nov. 16

At the foot of the mountains of undecidability

The limits of computation

Nov. 21

The limits of computation

Nov. 23

🥧

Computability

  • Read § 5.1–5.3
  • Read reductions handout
  • Assignment 10
  • ECS

Nov. 28

Computability and reductions

Nov. 30

The big picture

Review

Dec. 5

Exam 3 review

Dec. 7

📚

Final exams

Dec. 12

📝

Dec. 14

Exam 3
1:00–3:00 p.m.

Present-day computers are built of transistors and wires, but they could just as well be built, according to the same principles, from valves and water pipes, or from sticks and string. The principles are the essence of what makes a computer compute. One of the most remarkable things about computers is that their essential nature transcends technology.

W. Daniel Hillis, The Pattern on the Stone, 1998