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

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




CONTENTS  OF THE COURSE

Part I

Part II



TEXTBOOKS

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


LECTURE NOTES

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

HOMEWORK

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

EXERCISES

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