Computability Theory

Course Description and Grading
This is the first part of 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.

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

Course Meeting Time and Location
Tuesday and Thursday
1:00 - 2:25 pm
310 Linde

Course Instructor Contact Information and Office Hours
Office - 379 Linde

TA Contact Information and Office Hours



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

Course Policies
In each homework set, 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, previous years' solutions, the Internet, etc. 
Late submissions without prior approval from the instructor are not allowed except for medical problems or serious personal difficulties in which a note from the Dean's office is provided.

 Date PostedAssignment Due Date 

Collaboration Table
You may consult: 
Suggested or other booksYES
Solution manualsNO
Your notes (taken in class)YES
Class notes of othersYES
Your hand copies of class notes of othersYES
Photocopies of class notes of othersYES
Electronic copies of class notes of othersYES
Course handoutsYES
Your returned homeworkYES
Solutions to homework (posted on course webpage)YES
Homework / exams of previous yearsNO
Solutions to homework / exams of previous yearsNO
Emails from TA or the instructorYES
You may:
Discuss problems with othersYES
Look at communal materials while writing up solutionsYES
Look at individual written work of othersNO
Look up solutions to problems from any sourceNO