COURSE DIRECTOR	CLASSES
G. Tourlakis	Tuesday and Thursday
Room 2051, CSB	10:00  - 11:30 am
Telephone: 736-2100-1-66674	Classroom: R S101
e-mail: gt@cs.yorku.ca	York Campus

Computability or recursion theory addresses the question of what is, and what is not, "mechanically", or "effectively",
computable (once it gives a formal definition of what the terms in quotation marks ought to mean). Broadly speaking,
it studies recursive (or inductive) definitions on all sorts of mathematical structures.

This course discusses fundamental issues of computability and uncomputability and the close affinity between
computations and formal proofs, and concludes with a brief study of computational complexity (that deals
with questions of "efficiency": that is,  why some mechanically solvable problems seem to require enormous amounts
of computational resources for their solution, while others do not).

Topics include computable and semi-computable functions and relations; universal function and S-m-n theorems;
recursion theorem; unsolvable problems and Rice's Theorem; "strong" reducibilities; productive and creative sets;
the connection between uncomputability and unprovability (Godel's first incompleteness theorem, and Church's
undecidability of Hilbert's Entscheidungsproblem);  "oracle computations" and Turing reducibility.

We also sample topics from computational complexity, including Blum's abstract complexity axioms and some of their
consequences; polynomial time reducibilities; NP-hard and NP-complete problems; and Cook's theorem. We
conclude by revisiting creative sets and their connection with "inevitably long" formal proofs of "trivial" theorems.

Prerequisites. As published in the graduate calendar. Practically, the essential prerequisite for the course is a certain
degree of proficiency in following and formulating combinatorial arguments. Such proficiency should be normally
acquired by a student who has successfully immeresed herself or himself in the "proof culture" of courses such as
COSC 2001.03, COSC 3101.03, or MATH 2090.03.
Students who have not completed any of the above courses, but (strongly) believe nevertheless that they have
the equivalent background, should seek special permission to enroll in consultation with me.

Work-Load and Grading.

The course grade will be based mainly on about 3-4 homework assignments that will be completed
by students individually . 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.

Textbook.

• G. Tourlakis, Computability , Reston Publishing Company, 1984.

References.

(1) J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation,
Addison-Wesley.

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. __