A gentle introduction to the theory of computation. Nowadays, in the real world, we use computers to solve essentially all the problems we need to solve. But what are the limits of computation, if they exist? We will discuss this question in great detail, on the way discovering many wonderful concepts and a surprisingly elegant theory. Syllabus 1. Intro. What is complexity/computability theory and why do we care? Languages. The Turing Machine. The Church-Turing thesis. 2. Decidability. Examples of decidable problems. ATM and the diagonal argument 3. Reductions. Other undecidable problems. The Halting problem and the busy beaver function. 4. Big-O notation. P. The strong Church-Turing thesis. Examples of problems in P. 5. Non-deterministic computation. NP. Examples of problems in NP. Discuss P's relationship with NP. Space analogue: PSPACE = NPSPACE. 6. NP-Completeness. Cook-Levin Theorem. TQBF and PSPACE-completeness. 7. Cook-reductions. More NP-complete problems. 8. IP. Interactive protocols. Zero-knowledge. IP = PSPACE.

Come learn about the awesomeness of Tea! It helps me survive and it can help you too! Try new kinds of tea, tea with milk, tea with boba, tea with scones, tea with sandwiches, tea with cake, tea with dim sum, tea with math... the possibilities are endless!