Computer Science (COMP) 674

Theory of Computation (Revision 2)

COMP 674

Delivery Mode: Grouped Study Online

Credits: 3

Prerequisite: Students entering this course should have a strong background in discrete mathematics, data structures, and algorithms.

Students concerned they may not meet the prerequisites for this course are encouraged to contact the course coordinator before registering.

Faculty: Faculty of Science and Technology

Centre: School of Computing and Information Systems

Instructor: Dr. Dunwei (Grant) Wen

**Note:  This is a graduate level course and students need to apply and be approved to one of the graduate programs or as a non-program School of Computing and Information Systems graduate student in order to take this course.  Minimum admission requirements must be met.  Undergraduate students who do not meet admission requirements will not normally be permitted to take this course.


Computer Science 674 is an elective course in the "Theory Stream" of the MSc(IS) program. Central to the theory of computation are the concepts of automata, formal languages, grammar, algorithms, computability, decidability, and complexity. Why study theory when the current focus of Computer Science (and all the more so for Information Systems) is on technology and the pragmatic areas of knowledge concerned with the development and management of computer information systems? The reasons are manifold. Theory provides a simple, elegant view of the complex machine that we call a computer. Theory possesses a high degree of permanence and stability, in contrast with the ever-changing paradigms of the technology, development, and management of computer systems. Further, parts of the theory have direct bearing on practice, such as Automata on circuit design, compiler design, and search algorithms; Formal Languages and Grammars on compiler design; and Complexity on cryptography and optimization problems in manufacturing, business, and management. Last, but not least, research-oriented students will make good use of the theory studied in this course.

Course Objectives

The learning objectives of this course are to:

  1. introduce students to the mathematical foundations of computation including automata theory; the theory of formal languages and grammars; the notions of algorithm, decidability, complexity, and computability.
  2. enhance/develop students' ability to understand and conduct mathematical proofs for computation and algorithms.


Unit 0: Formation of Preliminary Concepts

  • Automata, computability, and complexity
  • Mathematical tools
  • Definitions, theorems, and proofs
  • Types of proofs

Unit 1: Regular Languages

  • Finite automata
  • Nondeterminism
  • Regular expressions
  • Nonregular languages

Unit 2: Context-Free Languages

  • Context-free grammars
  • Pushdown automata
  • Non-context-free languages

Unit 3: The Church-Turing Thesis

  • Turing machines
  • Variants of Turing machines
  • Definition of "algorithm"

Unit 4: Decidability

  • Decidable languages
  • The halting problem

Unit 5: Reducibility

  • Undecidable problems in language theory
  • A simple undecidable problem
  • Mapping reducibility

Unit 6: Advanced Topics in Computability

  • The recursion theorem
  • Decidability of logical theories
  • Turing reducibility
  • A definition of "information"

Unit 7: Time Complexity

  • Measuring complexity
  • The class P
  • The class NP
  • NP-completeness
  • NP-complete problems

Learning Outcomes

Upon successful completion of this course, you will be able to

  • discuss key notions of computation, such as algorithm, computability, decidability, reducibility, and complexity, through problem solving.
  • explain the models of computation, including formal languages, grammars and automata, and their connections.
  • state and explain the Church-Turing thesis and its significance.
  • analyze and design finite automata, pushdown automata, Turing machines, formal languages, and grammars.
  • solve computational problems regarding their computability and complexity and prove the basic results of the theory of computation.


To receive credit for COMP 674, you must achieve a cumulative course grade of B- (70 percent) or better, and must achieve an average grade of at least 60% on the assignments and 60% on the final examination. Your cumulative course grade will be based on the following assessment.

Assessment Weight
Assignment 1 (after Unit 2) 20%
Assignment 2 (after Unit 5) 20%
Assignment 3 (after Unit 7) 20%
Final Exam (2-day take-home) 40%
Total 100%

Course Materials


Sipser, M. (2006). Introduction to the Theory of Computation (2nd ed.). Boston, MA: Thompson Course Technology.

Other materials

The remaining learning materials are distributed in electronic format. At this time, these materials include:

  • Units 1 to 7 of the Study Guide.
  • A Study Plan listing the required course completion tasks in logical order.
  • Detailed descriptions of the requirements for each Assignment.

Additional supporting materials of interest to students may occasionally be made available electronically via the course website and conference.

Special Course Features

IS courses at Athabasca University require that students use computer-mediated communications. We expect students to have access to a computer with connection to the Internet.

Workload for Students in COMP 674

Students can expect to spend a weekly total of 5 to 25 hours on course work--depending on their level of mathematical maturity.

Special Note

Students registered in this course will NOT be allowed to apply for a course extension due to the nature of the course activities.

Athabasca University reserves the right to amend course outlines occasionally and without notice. Courses offered by other delivery methods may vary from their individualized-study counterparts.

Opened in Revision 2, April 18, 2012.