Simon Fraser University
Engaging the World

Course Outlines

Fall 2025 - CMPT 409 D100

Special Topics in Theoretical Computing Science (3)

Computability + Logic

Class Number: 5517

Delivery Method: In Person

Overview

  • Course Times + Location:

    Sep 3 – Dec 2, 2025: Tue, 2:30–4:20 p.m.
    Burnaby

    Sep 3 – Dec 2, 2025: Thu, 2:30–3:20 p.m.
    Burnaby

  • Exam Times + Location:

    Dec 15, 2025
    Mon, 8:30–10:30 a.m.
    Burnaby

  • Prerequisites:

    CMPT 307 with a minimum grade of C-.

Description

CALENDAR DESCRIPTION:

Current topics in theoretical computing science depending on faculty and student interest.

COURSE DETAILS:

Modern logic grew out of efforts to provide a formal foundation for mathematics in the early 20th century, at the centre of which are fundamental results by Godel, Turing, and other luminary figures, establishing close ties between logic and computation. Logic has turned out to be a powerful tool in computer science.  In fact, most working logicians today are computer scientists. This course will provide an introduction to basic results in logic and computability, including Godel's Incompleteness theorems.

Note: This course is cross-listed with CMPT 701.
Note: This course will be taught as CMPT 401 starting Fall 2026 with the following calendar description:

This course explores the nature and limitations of computation and logic, and how they are connected. Topics include: Computable functions, Church's thesis, computationally unsolvable problems, recursively enumerable sets; Predicate calculus, including the completeness, compactness, and Lowenheim-Skolem theorems; Formal theories and the Gödel Incompleteness Theorem.

Prerequisites: One of CMPT 307, PHIL 310, MACM 201; or a minimum of 6 upper division units in MATH. Quantitative.

COURSE-LEVEL EDUCATIONAL GOALS:

  • Propositional Logic
  • First-Order Logic
  • Proof System: Gentzen's calculus
  • Computability Theory
  • Recursive and Recursively Enumerable Sets
  • Goedel's Incompleteness Theorems

Grading

NOTES:

To be determined in the first week of classes. Typically, we have 4 assignments, tests and a final.

Materials

MATERIALS + SUPPLIES:

  • Computability and Logic - Course Notes, provided by the instructor, Stephen A. Cook, 0000000000000, These notes will be available as pdf files from the course web page.
  • A Mathematical Introduction to Logic, 2nd Edition., Herbert B. Enderton, Elsevier, 2001, 9780122384523
  • Introduction to the Theory of Computation, Michael Sipser, Cengage, 2012, 9781133187790

REQUIRED READING:

  • Computability and Logic - Course Notes, provided by the instructor, Stephen A. Cook, 0000000000000, These notes will be available from the course web page.

RECOMMENDED READING:

  • A Mathematical Introduction to Logic, 2nd Edition., Herbert B. Enderton, Elsevier, 2001, 9780122384523
  • Introduction to the Theory of Computation, Michael Sipser, Cengage, 2012, 9781133187790

REQUIRED READING NOTES:

Your personalized Course Material list, including digital and physical textbooks, are available through the SFU Bookstore website by simply entering your Computing ID at: shop.sfu.ca/course-materials/my-personalized-course-materials.

Department Undergraduate Notes:

The following are default policies in the School of Computing Science. Please check your course syllabus whether the instructor has chosen a different policy for your class, otherwise the following policies apply.
 
  • Students must attain an overall passing grade on the weighted average of exams in the course in order to get a C- or higher.
  • All student requests for accommodations for their religious practices must be made in writing by the end of the first week of classes, or no later than one week after a student adds a course. After considering a request, an instructor may provide a concession or may decline to do so. Students requiring accommodations as a result of a disability can contact the Centre for Accessible Learning (caladmin@sfu.ca).

Registrar Notes:

ACADEMIC INTEGRITY: YOUR WORK, YOUR SUCCESS

At SFU, you are expected to act honestly and responsibly in all your academic work. Cheating, plagiarism, or any other form of academic dishonesty harms your own learning, undermines the efforts of your classmates who pursue their studies honestly, and goes against the core values of the university.

To learn more about the academic disciplinary process and relevant academic supports, visit: 


RELIGIOUS ACCOMMODATION

Students with a faith background who may need accommodations during the term are encouraged to assess their needs as soon as possible and review the Multifaith religious accommodations website. The page outlines ways they begin working toward an accommodation and ensure solutions can be reached in a timely fashion.