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