# Notes - Computational Complexity HT25, Diagonalisation

> Source: https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/diagonalisation/ · Updated: 2025-05-24 · Tags: uni, notes

- [Course - Computational Complexity HT25](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/)
	- [Notes - Computational Complexity HT25, Basic definitions](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/basic-definitions/)
	- [Notes - Computational Complexity HT25, Hierarchy theorems](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/hierarchy-theorems/)
	- See also:
	- ["Diagonalisation"](https://complexityzoo.net/Complexity_Dojo/Diagonalization) at the Complexity Zoo

Diagonalisation is one of the few techniques we have for proving unconditional lower bounds on complexity classes.

### Flashcards
#### The halting problem
@Prove that the language
$$
L :=\mathsf{Accept_{TM} } = \\{\langle M, x \rangle : M \text{ accepts }x\\}
$$
is recursively enumerable but not decidable via a diagonalisation argument.::

$L$ is recursively enumerable since to decide membership we can just use a universal Turing machine to simulate $M$ on $x$.

But suppose that it is also decidable.

Construct a table $A$ where the rows are encodings of Turing machines and the columns are all possible strings. Set $A[i, j] = 1$ if and only if $M_i$ accepts $s_j$.

Construct a new language by flipping the diagonal, i.e. $s_i \in L' \iff \langle M_i, s_i \rangle \notin L$.

If $L$ is decidable, then $L'$ is also decidable. But if $L'$ is decidable, then there exist some Turing machine $M_i$ that appears among the rows of the table. This leads to a contradiction, since this Turing machine would have to accept $s_i$, but by definition it doesn't.

Hence $L$ cannot be decidable.

#### Time and space hierarchy theorems
See [Notes - Computational Complexity HT25, Hierarchy theorems](https://ollybritton.com/notes/uni/part-b/ht25/computational-complexity/notes/hierarchy-theorems/).
#### Other examples
Given a language $L \subseteq \lbrace 0, 1 \rbrace^\ast$, define the census function
$$
\begin{aligned}
&\text{cens}_L : \lbrace 1 \rbrace^\ast \to \mathbb N \\\\
&\text{cens}_L(1^n) = |L \cap \lbrace 0, 1 \rbrace^n|
\end{aligned}
$$
@Prove that there is a language $L \in \mathsf{DTIME}(2^n)$ such that $\text{cens}_L$ is not computable in time $O(2^{n/2})$.::

The idea is to use diagonalisation. Let $M_1, M_2, \ldots$ be an enumeration of the Turing machines such that each Turing machine occurs infinitely many times, and where these Turing machines compute corresponding functions $f_1, \ldots, f_n$.

We want to find some $M$ such that $\text{cens}_{L(M)}$ is not computed by any $M_i$ with runtime $O(2^{n/2})$ where $M$ runs in time $O(2^n)$.

- On input $x$:
	- Calculate the corresponding TM $M_i$
	- Run $M_i$ on $x$ of length $n$ for up to $2^n$ steps. If $M_n$ halts and outputs an integer $z > 0$, $M$ rejects, otherwise it accepts.

@example~ @exam~

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt