YORK UNIVERSITY

Department of Electrical Engineering and Computer Science

EECS 4111/EECS5111—Automata and Computability

Course Outline-Fall  2018

First day of class: September 5, 2018


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: MC 111

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.
We will lay the foundations of the theory using the Unbounded Register Machines of Shepherdson and Sturgis (URMs).
Topics will include: A mathematical model of computation (URMs);
Primitive Recursion and Loop Programs; Arithmetisation and Kleene's Predicate; Church's Thesis; Unsolvability via Diagonalisation and Reductions;
The Recursion Theorem; The connection between Uncomputability and Unprovability: Gödel's First Incompleteness Theorem through the Halting Problem;
The complexity of Primitive Recursive functions and relations via the hierarchy approach (Axt, Loop-Program, Grzegorczyk hierarchies) including the Ritchie-Cobham theorem.

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

The essential prerequisite for EECS4111/EECS5111 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 EECS2001.03 (or EECS3101.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 solely be based  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 EECS5111) 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.

NB. Notes beyond the text are posted on the course web site and are frequently updated.

Course Learning Outcomes.

By the end of the course, the students will be expected to be able to:

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: September 11, 2018.