Ma 117a:  Computability Theory (Fall 2016-17)



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.


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


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


Alexander Kechris
386 Sloan


Ronnie Chen
Sloan 382

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


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


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


Part I

Part II


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


Date Description
 10/3  Notes #1
 10/18  Notes #2
 10/24  Notes #3


Due Date Homework Solutions
 10/11  Homework #A  Solutions
 10/18  Homework #B  Solutions
 10/25  Homework #C  Solutions
 11/1  Homework #D  Solutions
 11/8  Homework #E  Solutions
 11/15  Homework #F  Solutions
 11/22  Homework #G  Solutions
 12/1 (note change in date)
 Homework #H  Solutions


Date Description
 9/28 Exercises #1 
 11/1 Exercises #2