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 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