Name: Theory of Computation
Author: Wei-Kai Lin

UVA CS 3120 Theory of Computation (Wei-Kai Lin)

This is the course website of CS 3120 (also called Discrete Mathematics and Theory 2), instructed by Prof. Lin. The meetings are Tuesdays and Thursdays at 9:30 - 10:45pm Spring 2026 and in Olsson 120.

Another section of the same course: Prof. Pettit also teaches this course in this Spring 2026. The two sections use different textbooks and proceed with slightly different topics although the overall goals are similar. The workload of this section shall be similar to the other section, but it is up to the staff’s discretion.

Recent Announcements

(List of announcements)

Class 28: Review, Gödel’s Imcompleteness Theorem

(Apr 28, 2026)

We reviewed the five modules in this course. As an exercise, we considered the set $S$ of infinite sequences of real numbers, $S = \{(a_0, a_1, a_2, \dots) ~\mid~ a_i \in \mathbb{R} \text{ all } i \}$, which is proved to be uncountable but the cardinality is the same as the real number set, $|S| = |\mathbb{R}|$. We also briefly introduced proof systems in the view of algorithms, and we showed a variant of Gödel’s Imcompleteness Theorem for statement of machines. Slides are here.

Quiz 13 is posted on Gradescope.

Class 27: Implication of P vs NP

(Apr 23, 2026)

We discussed the implications of P vs NP. An important one is that almost all cryptography assumes $\mathbf{P} \neq \mathbf{NP}$ at weakest (and it is possible we need stronger assumptions for crypto). Also, many other real-world combinatorics and optimization problems are NP-Complete. In addition, some popular video/computer games are proven to be NP-Complete. We wrapped up with discussing graph 3-coloring problem and proving it NP-Complete. Slides are here.

Class 26: Cook-Levin Theorem

(Apr 21, 2026)

We discussed and proved Cook-Levin Theorem. Particularly, we proved the theorem by a reduction from any problem in NP to CircuitSAT, and then another reduction from CircuitSAT to 3SAT. We also briefly showed an alternative definition of NP, where we defined Non-deterministic Turing Machines, and that is why NP is named by N. Slides are here.

Quiz 12 is posted on Gradescope.

Class 25: Class NP

(Apr 16, 2026)

We introduced the complexity class NP today. Many natural problems, including LongestPath, CircuitSAT, 3SAT, and COMPOSITE, are problems in NP, and we proved that $P \subseteq NP \subseteq EXP$. We then discussed the open question $P$ vs $NP$ with the definitions of classes co-NP, NP-Hard, and NP-Complete. Next, we will discuss and prove Cook-Levin Theorem. Slides are here.

Homework 8 is due this Friday. Homework 9 is coming soon.

Class 24: Reductions and SAT

(Apr 14, 2026)

Midterm 3 is finished! Our course continued with polynomial-time reductions. There are two different types of reduction, Karp reduction and Cook reduction, but in general, a reduction is just an algorithm that uses a subroutine for problem B to solves a problem A. We also introduced two satisfiability problems, CircuitSAT and 3SAT. We will introduce NP next. Slides are here.

Homework 8 is due this Friday. Theere is no quiz this week.

Class 23: Class EXP

(Apr 9, 2026)

We reviewed computability for the next Midterm 3, where reductions and Rice’s Theorem are important concepts. We continued with complexity with some graph problems, Shortest Path and Longest Path, and we introduced the class $\mathbf{EXP}$, which consists of functions computable in exponential time. We also talked about search and decision problems using Longest Path as an example. We will talk about polynomial-time reductions next. Slides are here.

Homework 8 is here.

Class 22: Class P

(Apr 7, 2026)

We wrapped up the module on computability and started the last module of this course, complexity. The purpose of complexity is to know how much computational resources is needed to solve problems. For Turing Machines and real-world programs, running time and space are two different kinds of resources. We briefly talked about the relation between time and space, and then we moved to time complexity classes, TIME(T). We ended at the class $\mathbf{P}$ of functions that are computable in polynomial time. Slides are here.

Quiz 11 is posted on Gradescope.

Class 21: Running Time

(Apr 2, 2026)

We recapped the statement of Rice’s Theorem, and we discussed in detail which functions are semantinc properties. We also introduced the running time of Turing Machines and the Busy Beaver function. With that, we are almost concluding the module of computability. Slides are here.

Class 20: Reductions, and Rice’s Theorem

(Mar 31, 2026)

We recapped the uncomputable function HALT, also called the Halting Problem, and then we discussed the theoretical and practical meaning of the theorem. Also, we formally introduced the concept of reduction. It is a useful framework to prove uncomputability, but it is also an essential technique to relate two seemingly unrelated problems. We introduced semantic properties and Rice’s Theorem. Slides are here.

Homework 7 is posted. Quiz 10 is coming soon and well be posted on Gradescope.

Class 19: Halting Problem

(Mar 26, 2026)

We recapped computability, and then we introduced our first uncomputable function, called Not-Self-Accepting or NSA for short. NSA is carefully defined (by our textbook) so that the proof of its uncomputability is more accessible through a diagonalization arugment (or more generally a proof by contradiction). Given that NSA is uncomputable, we proved that the Halting Problem is also uncomputable by “reduction.” Reduction is an extremely important technique and will appear multiple times in the coming weeks. Slides are here. Handout is here

Homework 7 is coming soon.

Class 18: Universal Turing Machine

(Mar 24, 2026)

Midterm 2 is finished! We recapped Turing completeness and showed many Turing complete programming languages games. We then defined universal Turing Machines, and we introduced “computability” as whether a function or a number can be computed by a Turing Machine. Next class, we will discuss computable and uncomputable functions using universal Turing Machines. Slides are here.

Quiz 9 is posted on Gradescope.

Class 17: Turing Completeness

(Mar 19, 2026)

We reviewed key concepts in the circuits module. Continuing on the topic of computability, we discussed more about Random-Access Machines (RAM). We informally argued that RAM is equivalent to Turing Machines (TM) in terms of computability. This also implies that many programming languages and computation models are “Turing complete,” meaning that they are equivalent to TM. We ended with introducing “computable numbers” that are discussed in Turing’s paper. Slides are here.

Class 16: Variants of Turing Machines

(Mar 17, 2026)

We considered other potential ways to define Turing Machine as a computation model. They include a larger alphabet, a two-way infinite tape, and using two tapes, and there are more other definitions in terms of input or input. We wrapped up with defining Random-Access Machines, and we will continue from here in the next meeting. Slides are here.

HW 6 is here. Quiz 8 is posted on Gradescope.

Class 15: Executing Turing Machines

(Mar 12, 2026)

We reviewed a couple of questions in Midterm 1, especially the finite memory of the Tamagotchi toy. That contrasts the infinite memory tape of the Turing Machine model. We continued with the executing of TM and the input and output formats. Although writing TM programs is not a major goal of this course, we looked at the palindrome example to see how TM works. We talked a bit about the life of Alan Turing, including that his photo and his writing are printed on the UK bank notes. Slides are here.

HW 6 is coming soon. Quiz 7 is posted on Gradescope.

Class 14: Introducing Turing Machines

(Mar 10, 2026)

We talked about a recent covering on Cantor and Dedekind, and we wrapped up the circuit module with the Physical Extended Church-Turing Thesis. Then, we introduced Turing Machines, which started the next module of this course. Slides are here.

HW 5 is posted. Quiz 7 is coming soon.

Class 13: Circuit size hierarchy

(Feb 26, 2026)

Chase Fickes lectured the theorem and the proof of circuit size hierarchy. Following the theorem, we talked about the lower bounds of circuit sizes briefly; notice that the circuit size hierarchy is a existential lower bound. Personally, I wish I had learned this theorem when I was an undergraduate, but it is more often skipped in many other courses on the theory of computation. Slides are here, which concatenates slides from Chase and me.

HW 5 is coming soon and due after Spring break.

Class 12: Program as Data

(Feb 24, 2026)

Midterm 1 is finished :D We continued with circuit sizes and showed that all $s$-gate circuits can be described in $O(s \log s)$ bits. That is a big idea! Using that representation, we can execute a string as program. Also, by counting the strings, we proved the existence of “hard” functions that cannot be computed using a small number of gates. Slides are here.

Quiz 6 is posted on Gradescope.

Class 11: Non-universal gates, and complexity

(Feb 19, 2026)

We reviewed Midterm 1 materials, but we also showed a non-regular language that satisfies the pumping properties. After that, we proved a set of gates that is not universal, and we introduced circuit size classes.
Slides are here.

Class 10: Universal circuits

(Feb 17, 2026)

We introduced straight-line programs using AND/OR/NOT gates, which is called a universal set of gates. Using those gates, we also showed that any $k$-bit input functions can be computed using $O(2^k)$ number of gates. Slides are here.

Quiz 5 is posted on Gradescope. HW 4 is posted here. Midterm 1 is next Tuesday, 9:30am, 20 minutes.

Class 9: NFA to DFA

(Feb 12, 2026)

We reviewed a couple of questions in Midterm 0; it aims to explain more generally how we ask and answer questions in this course. Then, we finished this Module with the construction from any NFA to DFA. Slides are here.

HW 4 is coming soon.

Class 8: Non-deterministic Finite Automata

(Feb 10, 2026)

We aimed to construct DFA from any regular expression, which is challenging. To do that, we defined non-deterministic finite automata (NFA), and we showed that we can construct NFA from any regular expression. Slides are here.

Quiz 4 is coming soon. Midterm 0 grades will be posted soon.

Class 7: DFA to Regular Expressions

(Feb 5, 2026)

We applied Pumping Lemma to show a few languages are not regular (i.e., some problems and functions can not be computed using DFA). Then, we proved that for every DFA, we can construct an equivalent regular expression. The idea is a cool recursion technique that breaks the a DFA into smaller sub-DFAs (and thus subproblems). Slides are here. HW 3 is here.

Class 6: Regular Expressions vs DFA

(Feb 3, 2026)

We finished Midterm 0 (yay~)! After that, we showed the powerful theorem, DFAs and Regular Expressions are equivalent, and its applications. They are positive results, and we went on with negative results and Pumping Lemma. Slides are here. Quiz 3 is posted on Gradescope.

Class 5: Regular Expressions

(Jan 29, 2026)

We talked about the syntax and evaluation of regular expressions. Then, we stated the equivalence between regular expressions and finite automata. We also reviewed the materials of Midterm 0 briefly. Slides are here. Homework 2 is coming soon.

Class 4: Cantor’s Theorem, Finite Automata

(Jan 27, 2026)

We proved Cantor’s Theorem, and then we introduced finite automata as the beginning of the next module. Slides are here. Quiz 2 is posted on Gradescope.

Class 3: Infinity

(Jan 22, 2026)

We defined Infinity, countable, and showed there are uncountable sets. Slides are here. Quiz 1 is posted on Gradescope. Homework 1 is posted.

We skipped a proof of the following theorem. Here is it.

Theorem: If a set $S$ is countably infinite, then $\card{S} = \card{\N}$.

We will prove that $\card{S} \le \card{\N}$ and $\card{S} \ge \card{\N}$ holds, which implies $\card{S} = \card{\N}$ by (Cantor-)Schröder–Bernstein Theorem.
We have $\card{S} \le \card{\N}$ by $S$ is countable.
It remains to prove that $\card{S} \ge \card{\N}$. That is, we want to show a surjective function $g: S \to \N$. Such $g$ is constructed (or described) below.
1. By $S$ is Dedekind infinite, there exists a strict subset $T\subsetneq S$ such that $\card{S} = \card{T}$.
2. By $\card{S} = \card{T}$, there is a bijection $f: S \to T$.
3. Let $U_0 = S$, and let $U_i = \{f(x) \mid x \in U_{i-1} \}$ for all natural numbers $i > 0$. That is, $U_i$ is the set of elements that are mapped from $U_{i-1}$ by $f$. Note that $U_1 = T$.
4. By strict subset, there exists $a_0 \in T, a_0 \notin S$.
5. Let $a_i = f(a_{i-1})$ for all natural numbers $i > 0$. We have $a_i \in U_i$ for all $i \in \N$ by definition of $U_i$ and $a_i$ (an induction is needed to be strictly formal).
6. Let $g$ to be the partial function that maps $a_i$ to $i$ (there may exists an element in $S$ that is not mapped to anything, so it is partial). This is the construction of $g$
It remains to argue $g$ is surjective.
Clearly, each $i\in\N$ is mapped from (or receives) exactly one element in $S$.
We want to argue that $a_i \neq a_j$ for all $i\neq j$, which implies that each element in $S$ is mapped to at most one natural number and that $g$ is surjective.
We claim that $a_i \notin U_{i+1}$ for all $i \in \N$.
Because $U_{j+1}\subseteq U_j$ for all $j\in\N$, the claim implies $a_i \notin U_j$ for all $i < j$.
Given that $a_j \in U_j$, the claim implies $a_i \neq a_j$ for all $i < j$.
1. To prove the claim, assume for contradiction, there exists $a_i \in U_{i+1}$ for some $i$ (for some $S$, bijection $f$, element $a_0$). Let $k$ be the smallest natural number satisfying such Property.
2. We have $k > 0$ as $a_0 \notin U_1$.
3. Since $f$ is a bijection, we have a unique $f^{-1}(a_k) = a_{k-1}$.
4. Since $f$ is a bijection and $f$ maps from $U_k$ to $U_{k+1}$, $f$ is also a bijection between $U_k$ and $U_{k+1}$.
5. By $a_k \in U_{k+1}$ and $f$ is bijective between $U_k$ and $U_{k+1}$, we have $f^{-1}(a_k) \in U_k$.
6. But $f^{-1}(a_k) = a_{k-1} \in U_k$ means $k-1$ also satisfy the Property, contradicting that $k$ is the smallest. This concludes the claim and the theorem.

Class 2: Cardinality

(Jan 20, 2026)

We talked about why study theory, infinite binary strings, and cardinality. Slides are here. Quiz 1 is coming in 24 hours.

Class 1: Definitions

(Jan 15, 2026)

We talked about constructive definitions, natural numbers, binary strings, and sets. Slides are here. Homework 0 is posted, which shall be submitted to Gradescope.

Class 0: Goals and grading

(Jan 13, 2026)

We talked about Karatsuba’s multiplication and grading. Slides are here. Quiz 0 is posted on Gradescope.

Tentative syllabus posted

(Jan 9, 2026)

Please take a look at the syllabus although it could change later.

List of Updates

UVA CS 3120 Theory of Computation (Wei-Kai Lin)
Recent Announcements
List of Updates