Course Description and Grading This is the first part of a threeterm 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 socalled 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 LocationTuesday 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
Notes
There is no textbook for this course. Here is a list of books on computability theory: H. Hermes, Enumerability, Decidability, Computability, SpringerVerlag, 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 NPCompleteness, W.H. Freeman, 1979.
 Handbook of Mathematical Logic, J. Barwise, Ed., NorthHolland, 1977.
 M. Machtey and P. Young, An Introduction to the General Theory of Algorithms, NorthHolland, 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, PrenticeHall, 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, PrenticeHall, 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.
Assignments Date Posted  Assignment  Due Date       
Collaboration Table  Homework 

You may consult:   Suggested or other books  YES  Solution manuals  NO  Internet  YES  Your notes (taken in class)  YES  Class notes of others  YES  Your hand copies of class notes of others  YES  Photocopies of class notes of others  YES  Electronic copies of class notes of others  YES  Course handouts  YES  Your returned homework  YES  Solutions to homework (posted on course webpage)  YES  Homework / exams of previous years  NO  Solutions to homework / exams of previous years  NO  Emails from TA or the instructor  YES  You may: 
 Discuss problems with others  YES  Look at communal materials while writing up solutions  YES  Look at individual written work of others  NO  Look up solutions to problems from any source  NO 

