ANNOUNCEMENTS

COURSE DESCRIPTION

This is a three term course providing an introduction to the basic concepts and results of the mathematical theory of computability and computational complexity theory.  It requires no essential prerequisites, except perhaps some familiarity with somewhat abstract mathematical reasoning, at the level of a course like Math 5.

The Fall term will be first devoted to the discussion of various theoretical models of computation, like Turing machines, register machines, Markov algorithms, and recursive functions.  We will demonstrate their equivalence and discuss Church's Thesis.  Then we will study the basic theory of computable functions and effectively enumerable sets on the integers.  We will use this theory to show that certain problems, like the so-called Halting Problem for Turing machines, are undecidable, i.e., cannot be solved algorithmically.

In the Winter term, we will discuss computability in the broader setting of mathematics.  Some of the highlights here are a development of the Gödel Incompleteness Theorems, the Boone-Novikov theorem on the undecidability of the word problem for groups, and the basics of the theory of algorithmic randomness.  We will also discuss many examples of undecidable problems from logic, number theory, group theory, combinatorics, and computer science.  No prior knowledge of any of these subjects is assumed.  We will develop all the necessary background.

In the Spring term, we will start with a discussion of decidable problems, i.e., problems for which there are actually algorithms for their solution.  Then we will introduce the basic concepts of the theory of computational complexity of algorithms.  We will study the concept of feasible (polynomial time) computation and the relationship between deterministic polynomial (P) and nondeterministic polynomial (NP) computations, including NP-complete problems and the famous "P = NP" problem.  We will also discuss probabilistic algorithms and derandomization.

PREREQUISITES

There are no essential prerequisites, except perhaps some familiarity with somewhat abstract mathematical reasoning, at the level of a course like Math 5.

SCHEDULE

TR, 1:00 - 2:30 PM, Sloan 151.

INSTRUCTOR

Alexander Kechris
386 Sloan
kechris@caltech.edu
626-395-4368

TA

Ronnie Chen
Sloan 382
rchen2@caltech.edu
626-395-4366

Office hours: Sunday 8:00 - 9:00 pm

GRADES

The grade for this course will be based on the homework assignments.

HOMEWORK POLICY

In each homework there will be one starred problem on which no collaboration is allowed.  For the other problems, collaboration is allowed but you should write up your own solutions.  You cannot look up solutions to the problems from any source, including books, earlier years' solutions, internet, etc.  Late submissions without prior approval of the instructor are not allowed except for medical problems or serious personal difficulties (note needed from the health center or Dean's Office).

TEXTBOOKS

There is no textbook for this course.  Here is a list of books on computability theory:

• H. Hermes, Enumerability, Decidability, Computability, Springer-Verlag, 1970.
• Y. Manin, A Course in Mathematical Logic for Mathematicians, Springer, 2010.
• M. Carey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.
• Handbook of Mathematical Logic, J. Barwise, Ed., North-Holland, 1977.
• M. Machtey and P. Young, An Introduction to the General Theory of Algorithms, North-Holland, 1978.
• A. Yasuhara, Recursive Function Theory and Logic, Academic Press, 1971.
• G. Boolos, J. Burgess and R. Jeffrey, Computability and Logic, Cambridge Univ. Press, 2002.
• N. Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge Univ. Press, 1980.
• M. Davis, Computability and Unsolvability, Dover, 1985.
• E. Engeler, Introduction to the Theory of Computation, Academic Press, 1973.
• M. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, 1967.
• B. Trakhtenbrot, Algorithms and Automatic Computing Machines, D.C. Heath, 1963.
• A. Malcev, Algorithms and Recursive Functions, Noordhoff, 1970.
• H. Lewis and C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1997.
• H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press, 1987.
• G. Tourlakis, Theory of Computation, Wiley, 2012.
• H. Enderton, Computability Theory, Academic Press, 2011.
• M. Sipser, Introduction to the Theory of Computation, Course Technology, 2005.
• M. Davis, R. Sigal and E. Weyuker, Computability, Complexity and Languages, Morgan Kaufmann, 1994.
• R. Weber, Computability Theory, Amer. Math. Society, 2012.
• D. Bridges, Computability: A Mathematical Sketchbook, Springer, 1994.

LECTURE NOTES

HOMEWORK

EXERCISES