Course Code MATH 643
Course Title Theory of Computation
Online Offers No offers currently scheduled.
Last offer: Fall 2020
Course Location Online
Credit Weight 0.5
Course Description

This course will use mathematics to study the foundations of problem solving and computation. A decision problem (answering "yes" or "no") can be characterized as a set of strings of characters encoding inputs that yield "yes" answers, and a computer can be characterized as a simple mathematical machine model that processes strings of characters. By studying properties of classes of problems of increasing complexity, we will be able to establish relationships among classes, membership in classes, and hard problems for classes. The course will culminate in the examination of classes and models that correspond to the power of computers, and the demonstration that there exist problems that cannot be solved.

Typical terms may not reflect online offerings.

Course Work and Exam Fall 2020 course outline (note 2)
Author(s) Naomi Nishimura
  • Corequisite: MATH 600, 692
Materials Software:
  • Some course components are not supported in Microsoft Edge.
System Requirements
  • A computer with Internet access is required for all online and multimodal courses. Please see the System Requirements.
Taught in English
Special Notes This course is only open to students in the Master of Mathematics for Teachers program.
How to Register:
Waterloo Students
Enrol In, Drop, and Swap Classes Online
How to Register:
Non-Waterloo Students
How to Apply - Prospective Students
Fees Tuition Fees, Financial Aid, Scholarships, and Awards

  1. The Undergraduate Calendar and the Graduate Calendar are the official source for information about course details. Quest is the official source for Undergraduate and Graduate Schedule of Classes information. The offerings indicated on this site are unofficial and subject to change daily. The course instructor will provide the official course requirements and expectations at the start of term.
  2. If available, the example of a recent course outline is provided for general information only. It gives an overview of the course from a recent offering but it is not the course outline for the current offer and is subject to change. If you are currently taking this course, the official course outline that applies to this offer is in your online course.
  3. Library Requirements: Please see the online library access and Waterloo ID card information.
  4. For a list of any required textbooks and other materials to be purchased, go to the Waterloo BookStore.