Mathematical Preliminaries for the Theory of Computation
Stub. The shared vocabulary for automata, computability, and complexity theory: sets, sequences/tuples, functions and relations, graphs, strings and languages, Boolean logic, and the standard proof techniques (construction, contradiction, induction) used throughout.
Corresponds to Sipser, Introduction to the Theory of Computation, Chapter 0. A glossary chapter rather than a theory chapter: fixes notation and terminology (sets, sequences, functions/relations, graphs, strings/languages, Boolean logic) used without re-explanation throughout automata, computability, and complexity theory, and reviews the three standard proof techniques — construction (build the object the theorem claims exists), contradiction, and induction — that essentially every proof in this topic area is one of.
Outline (TODO — flesh out each)
- Automata, computability, and complexity — how the three relate
- Sets; sequences and tuples; functions and relations; graphs
- Strings and languages; Boolean logic
- Definitions, theorems, and proofs
- Proof by construction, by contradiction, and by induction