Diagonalization

Automata

Prof. Calvin

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}\}) \]