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.pdf.

- Contents
- 1 Models of Computations; Polynomial Time & Church's Thesis.
- 2 Universal Algorithm; Diagonal Results.
- 3 Games; Alternation; Exhaustive Search; Time v. Space.
- 4 Nondeterminism; Inverting Functions; Reductions.
- 5 Randomness in Computing.
- References
- About this document ...

Wed Aug 21 20:35:42 EDT 1996