Theory of Computation

Venn diagram of some major computational complexity classes.

This is a course designed to teach you the mathematical foundations of computation, along with the techniques necessary to reason about structures that appear throughout computer science. Accordingly, the assignments in this course are designed to give you the chance to play around with the material and sharpen your skills with mathematical proofs, computability theory, and complexity theory. There will be nine homework assignments this semester, each of which is weighted roughly evenly. The Clay Mathematics Institute offers a $1 million reward for a proof to this question.

Course details



  • Mondays, 15.00 -- 16.00,
  • Tuesdays, 15.00 -- 16.00,
  • Wednesdays, 15.00 -- 16.00,


  • Thursdays, 15.00 -- 16.00,
  • Fridays, 15.00 -- 16.00,


  • Explore mathematical structures that arise in math and computing.
  • Equip you with the fundamental mathematical tools to reason about problems that arise in computing.
  • Explore the inherent complexity of problems and why some problems are harder than others.


  • We want you to have at least a basic familiarity with computer programming before taking the course, since many of the results we'll be exploring will be intimately connected to computers, computing, and programming. That said, there will be no actual programming assignments in this course. If you have not taken Alghoritms but are still interested in taking this course, I would suggest dropping by office hours so that we can chat about whether the course is a good fit for you.


# Week starting Content Lecture & Tutorial Activities Evidence
17 - 11 Sept 202000: Set Theory
  • Introduction to Set Theory
  • The Limits of Computation
  • [Slides 1]

  • This first problem set is designed to help you gain a familiarity with set theory and basic proof techniques. By the time you're done, you should have a much stronger sense of how to rigorously establish mathematical results.
  • Written reports and documentation source code. Exercises for develop skills in set theory.
  • 214 - 18 Sept 202001: Direct Proofs
  • Induction and Deduction
  • [Slides 2]

  • In the sciences, much reasoning is done inductively.
  • In mathematics, reasoning is done deductively.
  • This second problem set is designed to help you master inductive proofs. It begins with some simpler problems intended to help you adjust to induction, then concludes with applications to infinite series, recursive functions, and contests.
  • 321 - 25 Sept 202002: Finite Automata I
  • Finite automata
  • [Slides 3]

  • Finite automata are an abstraction of computers with finite resource constraints. Provide upper bounds for the computing machines that we can actually build.
  • For each of the following languages over the indicated alphabets, construct a DFA that accepts precisely those strings that are in the indicated language and begin with programing in python 3.
  • 428 - 30 Sept 202003: Finite Automata II
  • Non Finite Automata
  • [Slides 4]

  • An NFA is a Nondeterministic Finite Automaton
  • For each of the following languages over the indicated alphabets, construct an NFA that accepts precisely those strings that are in the indicated language and begin with programing in python 3.
  • 505 - 09 Oct 202004: Regular Languages
  • Regular Expressions and The Limits of Regular Languages
  • [Slides 5]

  • The regular expressions begin with three simple building blocks.
  • This fifth problem set explores the regular languages, their properties, and their limits.
  • 612 - 16 Oct 202005: Programming Regular Languages
  • Programming Regular Expressions
  • [Slides 6]

  • The regular expressions begin with programing in python 3.
  • This problem set explores the programming regular languages, their properties, and their limits.
  • 719 - 23 Oct 202006: Context-Free Languages and Grammars
  • Context-Free Grammars
  • [Slides 7]

  • A context-free grammar (or CFG) is an entirely different formalism for defining certain languages.
  • Below are a list of alphabets and languages over those alphabets. For each language, design a contextfree grammar that generates that language.
  • 826 - 30 Oct 202007: Pushdown Automata
  • Regular Expressions and the Limits of Regular Languages
  • [Slides 8]

  • the context-free languages, which are those that can be generated by context-free grammars. Is there some way to build an automaton that can recognize the context-free languages?
  • Any CFG can be converted into a PDA with just three states, meaning that the full power of the context-free languages can be expressed by three-state PDAs.
  • >
    902 - 06 Nov 202008: Defining Computability
  • The standard automaton for this job is the Turing machine.
  • [Slides 9]

  • A Turing machine is a finite automaton equipped with an infinite tape as its memory.
  • This problem explores Turing machines, nondeterministic computation, properties of the R and RE languages.
  • 1009 - 13 Nov 202009: Programming Turing Machines
  • Design a simple programming language that “compiles” down to Turing machines.
  • [Slides 10]

  • Keep extending our language to see just how powerful the Turing machine is.
  • Let's define the language Python to be other language with the introduction of a finite number of counters, variables that can hold arbitrary natural numbers. Initially, each counter holds the value 0.
  • 1116 - 20 Nov 202010: The Complexity Class P
  • The complexity class P (polynomial time) contains all problems that can be solved in polynomial time.
  • [Slides 11]

  • What problems do we believe are computationally intractable?
  • Given an undirected graph G = (V, E), a simple path in a G is a path between two nodes u, v ∈ V such that no node is repeated on the path.
  • 1223 - 27 Nov 202011: A nondeterministic Turing machine.
  • An NTM may have multiple transitions defined for a given state/symbol combination.
  • [Slides 12]

  • If we add nondeterminism to the DFA, we get the NFA.
  • For each statement below, decide whether the statement would definitely prove P = NP, definitely prove P ≠ NP, or would do neither.
  • 1301 - 04 Dec 202012: The Complexity Class NP.
  • The complexity class NP (nondeterministic polynomial time) contains all problems that can be solved in polynomial time by a single-tape NTM.
  • [Slides 13]

  • Nondeterministically guess how to fill in all the squares.
  • A graph coloring is a way of assigning colors to nodes in an undirected graph such that no two nodes joined by an edge have the same color.
  • Grading criteria



  • Theory of Computation, George Tourlakis 27 April 2012.
  • Introduction to the Theory of Computation. First Edition, Michael Sipser.
  • Teoría de Autómata y Lenguajes Formales: Dean Kelley. Prentice Hall.
  • Elements of the Theory of Computation: Harry Lewis, Cristos Papadimitriou.
  • Manual de lenguajes y gramaticas.
  • Resources


  • Resume for Set theory
  • Math type for homework
  • Tutorial markdown language
  • Tutorial markdown language
  • Install Perl on Windows
  • Install F# on Windows
  • Install Rust on Windows
  • Install and Use Git on Windows