Diagonalization
Automata
Sketch
- Undecidability
- (It’s non-trivial)
Goal
\[ \neg\text{Decidable}(A_{TM} := \{\langle M,w \rangle \space | \space w \in M:\text{TM}\}) \]
- We term this notion undecidability
- Review diagonalization first.
The Size of Infinity
Set Theory
- Diagonalization emerged from set and number theory.
- One way to show infinite sets have the same or different sizes is using bijections
Countability Lemma
\[ |\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| \]
Proof.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | \(\dfrac{1}{1}\) | \(\dfrac{1}{2}\) | \(\dfrac{1}{3}\) | \(\dfrac{1}{4}\) |
| 2 | \(\dfrac{2}{1}\) | \(\dfrac{2}{3}\) | ||
| 3 | \(\dfrac{3}{1}\) | \(\dfrac{3}{2}\) | \(\dfrac{3}{4}\) | |
| 4 | \(\dfrac{4}{1}\) | \(\dfrac{4}{3}\) |
Diagonalization Lemma
\[ |\mathbb{R}| \gt |\mathbb{N}| \]
\(Proof.\)
- 4.815998…
- That is, take an proposed bijection, and differ in the \(i\)’th digit from the \(i\)’th value.
- In fact, \(|\mathbb{R} = |2^\mathbb{N}|\)
Coming Attractions
- We have been storing computers as strings!
- We have been writing computers that study strings!
\[ \neg\text{Decidable}(A_{TM} := \{\langle M,w \rangle \space | \space w \in M:\text{TM}\}) \]