../

2026-08-26

Grading

  • Presenting (54%)
    • As Wei-Kai is teaching this class for the first time and he, selfishly, also wants to learn the material, each class will be prefaced by a student presentation
    • The presentation will largely summarize and prelude the topic to be covered that day
    • Each student will have to present 3 times this semester (Will change depending on the number of students still enrolled)
    • 10 minutes
    • Find interesting questions, etc.
  • Scribe Notes (36%)
    • As is the tradition in many mathematics courses, each class will have a scribe
    • The scribe notes are due a 1 week from the lecture date
    • Each student will have to scribe thrice
  • Problem sets
    • These are just for learning
    • They won’t be graded. Wei-kai doesn’t even have a TA
  • Quizzes (10%)
    • 2 x 20 minute quizzes
  • Class participation
    • Questions/answers during classes will be graded based on just presence and not accuracy

Turing Machines

  • These will be our primary (only) model of computation
  • As we will see, the mode of computation doesn’t really matter

It is much easier to see what a TM is with a diagram

  • It is just $k$ $\infty-$long tapes with discrete grid boxes
  • The first one is read-only and we call it the input tape
  • The rest are all working tapes and they are R/W. The last one of these is called the output tape
  • They are filled with some set of symbols that we’ll call the alphabet set $\Gamma$

Mathematical definition

More formally, a Turing machine is a quintuple $(\Gamma, Q, \delta, k)$

  • $Q$ the set of internal states of the Turing machine
    • $Q = [n], n\in \mathbb{N}$
    • We define $q_{\mathsf{halt}} = 0 \in Q$
  • $\Gamma$ Alphabets: the set of symbols allowed on the tape
    • The minimal one we’ll use is $\Gamma = {0, 1, \square, \triangleright}$
    • Here $\square$ is empty output and $\triangleright$ is the start position
  • $\delta: Q \times \Gamma^k \rightarrow Q \times \Gamma^{k-1} \times {\mathsf{L, R, S}}^{k}$ is the transition function which serves as the brain of the TM

Why care about TM

  • Turing machines can simulate many algorithms
    • In fact, almost all physically realizable things can be modeled as a TM
  • TM is simple (arguably simplest) model of computation
    • Other modes of computation have existed like $\lambda$-calculus and they are all equally expressive as TM but none of them are as simple

Magic the gathering, minesweeper and minecraft can implement a TM. Therefore can implement any concieveable algorithm.

TM equivalence

  • You may notice that there are a few knobs in the parameters of a TM. does that mean some TM are more powerful than others? No. It can be proven that all TM can be simulated by the smallest one.

$$ \forall M: |\Gamma| > 4, k >2, T(n) $$ $$ \exists M^: |\Gamma^| = 4, k^* = 2, T^2(n)\cdot \text{poly}(k, \log (|\Gamma|)) $$ The smallest TM can efficiently simulate all other TM

Do we need $|\Gamma| = 4$ can we do even smaller?

Technically we can do $|\Gamma| = 2$ but it is very cumbersome. So we consider the smallest TM to have 4 symbols.

Busy Beaver

Given a constant $|\Gamma|$ and $|Q|$ how long can a terminating TM run? Turns out very long. For even $n=6$ we don’t know. It is not possible to compute how many transitions a TM will run for.

Uncomputability

TM computes a function $f: {0, 1}^* \rightarrow {0, 1}$ iff $\forall x \in {0, 1}^*, M(x) = f(x)$ and $M(x)$ takes less than $T(|x|)$ steps

A function $f$ is computable if $\exists$ a TM that computes $f$

$\exists$ at least one $f$ that is not computable by any TM or Any TM cannot compute all possible $f$

Let $\mathsf{HALT}$ be the following function

$$ \mathsf{HALT}(\alpha, x) = \text{if } M_{\alpha}(x) \text{ halts } 1 \text{ otherwise } 0 $$

There is no TM that can compute this. Closely related to Godel’s incompleteness theorem