Formal models of computation to have the language and tools:
- what is computation?
- what can and cannot be computed?
- what can and cannot be efficiently computed?
Sidebar: proof
Goal
- basic principles of the theory of computation
- formalize and prove properties of computation
- apply basic principles of computational thinking such as reductions
- exposure to different areas of theory
Questions for Omer
Content
Finite Automata
this is a very simple model of computation (a constant amount of memory), meaning we can:
- characterize what can be computed (closure properties)
- non-determinism (power of verified guessing)
- characterize what cannot be computed
- optimization and learning
More modern (complexity-theoretic) perspective: streaming algorithms, communication complexity.
Turing Machines!!
turing machines are super powerful, meaning we can:
undecidability: characterize what can’t be computed (undecidability)
- understand problems through reduction
- hierarchy of exceedingly hard problems
- kolomogorov complexity (universal theory of information)
this builds the foundations of mathematics through computation
complexity theory
- time complexity
- P vs. NP, NP-completeness
- NP non-determinism
- SAT—likely hard to compute
- better reductions — polynomial reductions
- again, a hierachy of exceedingly hard problems
also adds: space, randomness, communication, power, etc.