YORK UNIVERSITY
Department of Computer Science and Engineering
CSE4111/CSE5111—Automata and Computability
Course Outline-Winter 2013
First day of class: January 7, 2013
COURSE DIRECTOR | CLASSES (see also Lecture Schedule ) |
G. Tourlakis | Monday and Wednesday |
Room 2051, LAS |
11 :30 - 13:00 |
Telephone: 416-736-2100 (ext. 66674) | Classrooms: CB122 |
e-mail: gt@cse.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.
We will lay the foundations of the
theory using the Register Machines of Shepherdson and Sturgis. Topics
will
include: Church's
Thesis; Primitive
recursion and Loop
Programs; Unsolvability via Diagonalisation and Reductions;
The Recursion Theorem; 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
(e.g., polynomial-time).
Prerequisites. General
Prerequisites, including CSE 3101 3.0 and, by transitivity, MATH1090 3.0 and
MATH(CSE)1019 3.0 or
similar courses.
The essential
prerequisite for CSE4111/CSE5111 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
CSE2001.03 (or CSE3101.03) and MATH 1090.03.
Ideally (but not absolutely necessarily) the student should be familiar with the mathematical topics that are reviews 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.
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 CSE5111) 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).
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: December 25,
2012.