YORK UNIVERSITY
Department of Electrical Engineering and Computer Science
EECS 4111/EECS5111—Automata and Computability
Course Outline-Fall 2021
First day of classes: September 8, 2021, at 11:30am. All following classes at 8:30am.
COURSE DIRECTOR | CLASSES (see also Lecture Schedule ) |
G. Tourlakis | Mondays and Wednesdays |
Room 2051, LAS |
8:30 - 10:00 |
e-mail: gt@cse.yorku.ca | Classrooms: By Zoom via eClass |
It is the responsibility of students to check the course web page weekly for course related information.
So, the plan is to
Topics will include: A mathematical model of computation (URMs); Primitive Recursion and Loop Programs; Church's Thesis; Universal and S-m-n theorems; Kleene's Predicate; 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.
This course delves deeper
into work that started in EECS 2001.
Prerequisites. General
Prerequisites,
including EECS 3101 3.0 and, by transitivity, EECS 2001, 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
a problem is
unsolvable", or "prove that such-and-such function is
primitive recursive", etc.
Graduate students in
the course (registered in EECS5111) will be
assigned additional
problems and readings,
and will be expected to probe the material further and deeper through the
completion of these problems.
The concept of "late
assignments" does not exist
(because solutions
are posted
typically on the due
date).
Official textbook.
Additional
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: Aug. 26,
2021.