These are notes for a Theory of Computation course. The goal is to introduce students to basic concepts of Theory of Computation and to provoke their interest in further study. Model-dependent effects are systematically ignored. Concrete computational problems are considered only as illustrations of general principles. The notes can be used by an instructor designing a course or by students who either know the material and want to refresh the memory or are exceptionally bright and have access to an instructor for questions. Each subsection takes about a week of the course.

Contents

1. Basics
   1. Deterministic Models; Polynomial Time & Church's Thesis
      1. Rigid Models
      2. Pointer Machines
      3. Simulation
   2. Universal Algorithm; Diagonal Results
      1. Universal Turing Machine
      2. Uncomputability; Goedel Theorem
      3. Intractability; Compression and Speed-up Theorems
   3. Games; Alternation; Exhaustive Search; Time vs. Space
      1. How to Win
      2. Exponentially Hard Games
      3. Reductions; Non-Deterministic and Alternating TM; Time and Space
2. Mysteries
   4. Nondeterminism; Inverting Functions; Reductions
      1. An Example of a Narrow Computation: Inverting a Function
      2. Complexity of NP Problems
      3. An NP-Complete Problem: Tiling
   5. Probability in Computing
      1. A Monte-Carlo Primality Tester
      2. Randomized Algorithms and Random Inputs
      3. Arithmetization: One-Player Games with Randomized Transition
   6. Randomness
      1. Randomness and Complexity
      2. Pseudo-randomness
      3. Cryptography
3. End Matter
   7. Go On!
   8. Writing Contributions
   9. References