COURSE DIRECTOR	CLASSES (see also Lecture Schedule )
G. Tourlakis	Monday and Wednesday
Room 2051,  LAS	14 :30  - 16:00
e-mail: gt@cse.yorku.ca	Classrooms: CB 129
	York Campus

Our main aim will be a thorough study of Computability and an introduction to Complexity.
We will lay the foundations of the theory using the Register Machines of Shepherdson and Sturgis. Topics will
include: Church's Thesis; Primitive recursion and Loop Programs; Unsolvability via Diagonalisation and Reductions;
The Recursion Theorem; The connection between Uncomputability and Unprovability: Gödel's Incompleteness Theorem through the Halting Problem;
Blum's axioms for Complexity; "Feasible" and "Unfeasible" computations: P, NP, and NP-complete problems;
Cook's theorem; More reductions (e.g., polynomial-time).

Prerequisites. General Prerequisites, including CSE 3101 3.0 and, by transitivity, MATH1090 3.0 and MATH(CSE)1019 3.0 or
similar courses.

The essential prerequisite for CSE4111/CSE5111 is a certain degree of proficiency in following and formulating
combinatorial arguments. Such proficiency should be normally acquired by a student who has successfully
completed a course such as CSE2001.03 (or CSE3101.03) and MATH 1090.03. 

Ideally (but not absolutely necessarily) the student should be familiar with the mathematical topics that are reviewed in the first chapter of the text. Students should visit said chapter as frequently as needed.

Students who have not completed any of the above courses, but who (strongly) believe nevertheless that they have
the equivalent background, should seek special permission to enrol in consultation with the instructor who can assess whether
indeed the equivalent background is in hand. This is a necessary condition for admission to the course without the on paper prerequisites. The EECS-gpa requirement cannot be waived.

Work-Load and Grading.

The course grade will be based mainly on about 3-4 homework assignments that will be completed
by students individually. These will be equally weighted. There will be no programming problems, but each assignment
will consist of a number of theoretical problems, for example "prove that such-and-such
function is not computable", or "prove that such-and-such function is primitive recursive", etc.

Graduate students in the course (registered in CSE5111) will be assigned additional homework and readings,
and will be expected to probe the material further and deeper.

The concept of "late assignments" does not exist (solutions are posted typically on the due date).

Official textbook.

• G. Tourlakis, Theory of Computation, Wiley, 2012.
  

• Define the concepts of “computation”, and “computable” and “uncomputable” functions, “decidable”, “semi-decidable” (or “recursively enumerable”) and “undecidable” decision problems in terms of both high level (e.g., Unbounded Register Machines) and low level (e.g., Turing Machines) models of computation.
• Design programs in both the Register and Turing Machine formalisms that compute specified functions or solve specified decision problems.
• Define Church’s Thesis and use it fluently to design “pseudo programs” that compute functions or decide/semi-decide decision problems.
• Prove undecidability and non-semi-decidability results via diagonalisation and/or reduction arguments.
• Understand and reproduce the argument that connects uncomputability in the theory of computation with unprovability in logic: Gödel's Incompleteness Theorem through the halting problem.
• Define “feasible” and “unfeasible” computations as well as the sets of decision problems P, NP, NP-hard and NP-complete.
• Understand and reproduce the argument that proves Cook's theorem.
• Perform poly-time reductions to show that a decision problem is NP-hard or NP-complete.
  

References.

(1) G. Tourlakis, Computability, Reston Publishing Company, 1984.

For more on Primitive Recursive and (total) Recursive functions see:

(2) R. Péter, Recursive Functions, Academic Press (Number-theoretic approach, rigorous, fairly difficult).

For more on unsolvability of concrete problems of combinatorial or number theoretical nature, see:

(3) M. Davis, Computability and Unsolvability, McGraw-Hill (Turing approach, rigorous, fairly difficult).

Matijasevic’s proof of the unsolvability of Hilbert’s 10th problem, using methods initiated by Davis
in (3) can be found in:

(4) Y.I. Manin, A Course in Mathematical Logic, Springer-Verlag (quite difficult).

For more on recursion theory, in general, see:

(5) H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill (Semi-formal
using Church’s thesis throughout; difficult).

Finally, for more on machines (at an elementary level), see:

(6) M. Minsky, Computation; Finite and Infinite Machines, Prentice-Hall. __
 
 
 
  Last changed: January 9, 2017.