Computability and Complexity

EECS 4111.03F Fall 2016

News and Announcements:

Re Assignment 5: I mentioned in class that for question 1A you can use 3SAT instead of SAT.
This makes it easier to prove that the Verifier is polynomial.
Nov 8: If you wish you can bring one page of notes to the test.
Material on page 79 concerning graph(f) has not been covered and is not included.
Nov 7: Test 2 includes everything up to today, except there will be nothing on Turing machines
Nov 2: Slides from lecture 15 are here for a few days
Nov 2: I encountered some notes by Yurii Khomskii that you might find helpful as an overview of some of our material (but ignore section 4.2). But there are lots of differences, e.g. he considers Turing machines rather than register machines, and there are some changes of notation e.g. he uses "c.e" instead of "r.e." This is not required reading, but could be useful for some. Revision to Assignment 4. Question 3b is replaced by a new question 4.

Q4: Show that A5 = {x | {x}1(5) = 5} is many-one reducible to K.
Note that this reduction is in a different direction (to K instead of from K), so it proves what ?
October 26:
Assignment 4 (see revision above)



Prof. Patrick Dymond
LAS 3052C

Office hours after class or by appointment or email.


Monday, Wednesday, 11:30 - 13:00, PSE 321, Petrie
except that the 4111 lecture of September 19 is planned to start at 12 noon.

Please be aware: Late enrollment in the course is not workable unless the student has been attending classes since the the first lecture,
and has kept up with readings and assignments. Attendance will be taken to provide documentation for any such cases.


Notes: Stephen A. Cook, Computability. (Handouts).

Here's the first installment of Professor Stephen Cook's course notes that we will be using.

Here's the second installment of Steve Cook's course notes that we will be using.

Book: Michael Sipser, Introduction to the Theory of Computation, (second or third edition) PWS Publishing Company, 2006.

We will start with Cook's computability notes. These will be followed by Sipser Chapters 4, 5.3 and 7, and familiarity with material in Sipser Chapter 3 and earlier chapters will be needed.

Lists of Errata for the Sipser book can be found here.

Here are some other useful references


This is a course in the mathematical theory of computation. It is intended to give a detailed understanding of the basic concepts of abstract machines, information flow, computability, and complexity. The emphasis will be on appreciating the significance of these ideas and the formal techniques used to establish their properties (i.e. constructions and proofs.) Topics chosen for study include: models of computation, primitive recursive and partial recursive functions, the Church-Turing thesis, limits to computation (undecidablility), reducibility, Rice's theorem and the recursion theorem, Godel's theorem, productive and creative sets, and the intrinsic difficulty of computational problems (especially NP-completeness).


CSE 2001, CSE 3101, general fourth-year CSE prerequisites.

Course Requirements:

Students complete the York University Academic Honesty Tutorial and attend and participate in the twice-weekly classes, read assigned material from the text in advance of corresponding lectures and prepare individual, correct, well-written, neat answers for weekly homework exercises.

The weekly homework component counts for 30% of the final grade. There will also be three eighty minute midterm tests, the first two each counting for 25% and the last one counting for 20% of the final grade. The tests are currently scheduled to held in class on October 12, November 9 and December 5. I will provide notice in class of any changes.

Please note that there is no provision for making up late exercises, assignments or missed classes or tests. Without sufficient medical documentation that you were both unable to perform the required tasks and unable to contact the instructor throughout the period prior to the scheduled date, missed material is to be assigned a score of zero. If problems arise in meeting a deadline, please contact the instructor by email or after class well in advance.
Students must avoid all forms of academic dishonesty including plagiarism and must fully cite all resources used and all help received in preparing solutions to exercises and assignments. It is allowed to verbally discuss homework problems in general terms only (not detailed solutions) with another student (not a group), but each student must undertand and prepare their writeup of the solution entirely on their own and must not not share it (or drafts of it) with others. Acknowledge all ideas obtained from others. Do not copy solutions found on the internet. Searching the internet to use someone else's solution to a problem is plagiarism, unless the student's submission explicitly and precisely explains the use of, and cites the source for, each of the ideas used. Plagiarism is unlikely to help a student pass the course, and it could result in the student losing their degree. Please also read over the department, faculty and University policies concerning academic honesty. The consequences of academic dishonesty are generally severe in fourth year courses. Decisions about violations and the penalites are made by the Associate Dean and/or the responsible Lassonde Faculty committee.

Course Schedule and Readings:

Please read the material to be covered in each class in advance of the lecture. The readings will be specified in class.

  1. Lecture 1: Notes 54-56 Intro + Register machine computable
  2. Lecture 2: Notes 56-58 Primitive recursive functions, diagonalization
  3. Lecture 3: Notes 58-60 Ackermann's function, minimization, RM composition
  4. Lecture 4: Notes 60-62 Recursive functions, LOOP and WHILE programs
  5. Lecture 5:
  6. Lecture 6:
  7. Lecture 7:
  8. Lecture 8:


A list of related reference books is available.