YORK UNIVERSITY

Department of Computer Science

COSC4111/5111—Automata and Computability

Course Outline-Fall  2004

First day of class: September 9, 2004


COURSE DIRECTOR CLASSES (see also Lecture Schedule )
G. Tourlakis Tuesday and Thursday
Room 2051, CSEB 13 :00  - 14:30
Telephone: 736-2100-1-66674  Classroom: PSE 321
e-mail: gt@cs.yorku.ca York Campus

It is the responsibility of students to check the course web page weekly for course related information.

Our main aim will be a thorough study of Computability and an introduction to Complexity.
Topics will be chosen from Turing computability and Kleene computability. Church's Thesis.
Primitive recursion and Loop Programs, Unsolvability via Diagonalisation and Reductions.
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.

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

The essential prerequisite for COSC 4111/5111 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 COSC 2001.03 (or COSC 3101.03) and MATH 1090.03.
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.

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.

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

Textbook.

NB. The text is available via the Reserve Steacie Library since it is out of print.

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