CSCI 341 Theory of Computation

Fall 2025, with Schmid

Table of Contents

References

These course notes did not come from nowhere! Section 1 is largely based on Todd's notes on automata theory, except for the puzzles and games in those subsections. Section 2 is very standard material, based on the textbook of Sipser and the classic textbook of Hopcroft, Motswani, and Ullman. The \(\lambda\)-calculus subsection is directly based on a set of notes from a course taught by Peter Selinger at Dalhousie.

Source Material

All of the writing in these notes and the in the references for the course lecture structure given above should be considered secondary sources. They aren't the original papers where the ideas behind the concepts were introduced. Below is a list of the original source material for each topic.

Top