Leonid A. Levin. Fundamentals of Computing.

These are notes for the course CS-172 I first taught in the Fall 1986 at UC Berkeley and subsequently at Boston University. The goal was to introduce the undergraduates to basic concepts of Theory of Computation and to provoke their interest in further study. Model-dependent effects were systematically ignored. Concrete computational problems were considered only as illustrations of general principles. The notes (prepared by the students and revised by me) are skeletal: they do have (terse) proofs, but exercises, references, intuitive comments and examples are missing or inadequate. The better is English in a paragraph the smaller was my contribution and the greater caution is needed.

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. A version of this notes appeared in SIGACT News; 22(1) 1991, 27(3) 1996. The most recent version is at http://www.cs.bu.edu/fac/lnd/toc/z.ps (or z.dvi).

Acknowledgments.

• Contents
• 1 Models of Computations; Polynomial Time & Church's Thesis.
  • 1.1 Deterministic Computation.
  • 1.2 Rigid Models.
  • 1.3 Pointer Machines.
  • 1.4 Simulation.
• 2 Universal Algorithm; Diagonal Results.
  • 2.1 Universal Turing Machine.
  • 2.2 Uncomputability; Goedel Theorem.
  • 2.3 Intractability; Compression and Speed-up Theorems.
• 3 Games; Alternation; Exhaustive Search; Time v. Space.
  • 3.1 How to Win.
  • 3.2 Exponentially Hard Games.
  • 3.3 Reductions; Non-Deterministic and Alternating TM; Time and Space.
  • 3.4 Fast and Lean Computations.
• 4 Nondeterminism; Inverting Functions; Reductions.
  • 4.1 Example of a Narrow Computation: Inverting a Function.
  • 4.2 Complexity of NP Problems.
  • 4.3 An NP-Complete Problem: Tiling.
• 5 Randomness in Computing.
  • 5.1 A Monte-Carlo Primality Tester.
  • 5.2 Randomized Algorithms and Random Inputs.
  • 5.3 Randomness and Complexity.
  • 5.4 Pseudo-randomness.
  • 5.5 Cryptography.
• References
• About this document ...