YORK UNIVERSITY
Department of Computer Science
COSC4111/5111—Automata and Computability
(This course also counts towards a Graduate Mathematics degree.)
Course Outline-Fall 2001
First day of class: September 6, 2001
Catalogue Number: 749001
COURSE DIRECTOR | CLASSES (see also Lecture Schedule Information) |
G. Tourlakis | Tuesday and Thursday |
Room 2051, CSB | 11:30 - 13:00 |
Telephone: 736-2100-1-66674 | Classroom: CCB 120 |
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.
We will initially study some advanced
topics in Automata and Language theory that build on your previous
knowledge (obtained in COSC 2001). For
example, we may look at the Myhil-Nerode theorem for automata,
extensions of the pumping Lemma for CFL,
Parikh's theorem.
Our main aim, however, 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 and reductions,
Godel'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.
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 / 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 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.
Textbooks.
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. __