Computability and Complexity

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.

Q4: Show that A

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)

Welcome.

LAS 3052C

email: dymond@cs.yorku.ca

Office hours after class or by appointment or email.

Monday, Wednesday, 11:30 - 13:00, PSE 321, Petrie

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.

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.

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

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