SFU                       Computing Science                       05-3
________________________________________________________________________
CMPT 701-3 G100"    Computability and Logic
 Instructor: D. Mitchell                     SFU Burnaby

________________________________________________________________________

OBJECTIVE/DESCRIPTION:

Deep connections between logic and computation have been evident since
early work in both areas.  More recently, logic-based methods have led to
important progress in diverse areas of computing science.  This course will
provide a foundation in logic and computability suitable for students who
wish to understand the application of logic in various areas of CS, or as
preparation for more advanced study in logic or theoretical CS.

TOPICS:

   o Propositional Logic
   o First-Order Logic
   o Proof Systems
   o Computability
   o Recursive and Recursively Enumerable Sets
   o Godel's Incompleteness Theorems

GRADING:

To be discussed in the first week of classes.

TEXTBOOKS:

   o None

RECOMMENDED:

   o A Mathematical Introduction to Logic, 2nd Edition., Herbert B.
     Enderton, Harcourt/Academic Press, 2001

REFERENCES:

   o A Course in Mathematical Logic, Bell, J. and Machover, M., Elsevier
     Science, 1977
   o Engines of Logic:  Mathematicians and the Origin of the Computer,
     Martin Davis, W.W. Norton, 2001

PREREQUISITES/COREQUISITES:

Willingness to work with material at a certain level of abstraction and
rigour.  If in doubt, please contact the instructor.

Distributed:  July 15, 2005

.......................................................................

Academic Honesty plays a key role in our efforts to maintain a high
standard of academic excellence and integrity.  Students are advised that
ALL acts of intellectual dishonesty are subject to disciplinary action by
the School; serious infractions are dealt with in accordance with the Code
of Academic Honesty (T10.02)
(http://www.sfu.ca/policies/teaching/t10-02.htm).  Students are encouraged
to read the School's policy information
(http://www.cs.sfu.ca/undergrad/Policies/).