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 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. SU-CS154 Week 1 SU-CS154 Week 2 SU-CS154 Week 3 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 SU-CS154 Week 4 SU-CS154 Week 5 SU-CS154 Week 6 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. SU-CS154 Week 7 SU-CS154 Week 8 SU-CS154 Week 9 …the end! SU-CS154 Week 10 and CS154 Final Summary