Simon Fraser University
Engaging the World

Course Outlines

Spring 2026 - CMPT 308 D100

Computability and Complexity (3)

Class Number: 5445

Delivery Method: In Person

Overview

  • Course Times + Location:

    Jan 5 – Apr 10, 2026: Tue, 1:30–2:20 p.m.
    Burnaby

    Jan 5 – Apr 10, 2026: Thu, 12:30–2:20 p.m.
    Burnaby

  • Prerequisites:

    (MACM 201 or CMPT 210) with a minimum grade of C-.

Description

CALENDAR DESCRIPTION:

Formal models of computation such as automata and Turing machines. Decidability and undecidability. Recursion Theorem. Connections between computability and logic (Gödel’s Incompleteness). Time and space complexity classes. NP-completeness.

COURSE DETAILS:

This course will discuss theoretical results concerning regular, deterministic, context free, context sensitive, and recursively enumerable languages via generative grammars and corresponding automata (finite state machines, push-down machines, and Turing machines). We will discuss a close connection that exists between automata and logic.

Topics include complexity bounds for recognition, language decision problems, operations on languages, first-order logic, Monadic second-order logic and its connection to regular languages, the famous Incompleteness Theorem of Godel.

Grading

NOTES:

Grading will be discussed in the first week of classes

Materials

REQUIRED READING:

Introduction to the Theory of Computation 3rd Edition

Michael Sipser,
Cengage Learning,
2012

 


ISBN: 9781133187790

RECOMMENDED READING:

Introduction to Automata Theory, Languages and Computation - 3rd Edition, J.E. Hopcroft , Rajeev Motwani, J.D. Ullman, Addison Wesley, 2006
ISBN: 9780321455369

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.