CS 365: Models of Computation

(See here for the 2021 edition of the notes.)

Preface

In these pages, you will find a set of lessons that provide an introduction to the theory of computation. These notes have been developed for the CS 365 course at the University of Waterloo.

If you are enrolled in the class, you can find all the information for the class itself on the course Learn page.

If you are not enrolled in the class, you are still most welcome to use these notes in your own independent study as well. Theoretical computer science is a rich area of mathematical research with many beautiful results and fascinating open problems that offer plenty of rewards for your efforts.

The main goal of these notes is to give a broad overview of the various facinating topics studied in theoretical computer science, with the hope that this foundation will leave you ready to begin exploring your own interests in the field. Unlike an earlier version of these notes, the proofs for the main results in these notes are included. However, they are initially hidden in collapsed subsections, and you are strongly encouraged to attempt to prove each result independently before reading the proof presented in the notes. The material is organized so that all of the proofs can be completed independently, and each attempt (whether successful or not) not only allows you to understand the material more deeply as you learn it, but also gives you the experience, tools, and confidence to go far beyond the topics covered in the notes themselves.

Happy explorations!

Eric Blais
Waterloo, ON, Canada
January 5, 2023