# Notes: Uncountable, Undecidable, Incompressible

• Rationals are countable. Map each pair $(a,b)$ to a unique natural number.
• Reals in $[0,1]$ are uncountable. Assume, for a contradiction that they are countable. Construct a real whose i’th digit is 0 if the i’th digit of the i’th number is odd and 1 otherwise. Then this number has some index t. The t’th digit of the number gives us a contradiction.
• Finite strings are countable, infinite (even binary) strings are uncountable.
• Diagonalization is the proof technique we used for showing sets are uncountable and languages are undecidable.
• Here’s a different proof of the existence of an undecidable language.
• For a binary string $x$, let $K(x) = \min \{ ||+|y| : M \mbox{ is a Turing machine}, M \mbox{ on input } y \mbox{ outputs } x \}$. In words, it is the shortest string including the description of a Turing machine and an input on which the TM produces the desired string $x$.
• Claim 1. For every integer $n > 1$, there is a string $x \in \{0,1\}^n$ s.t. $K(x) \ge |x|$.
• Define $L_K = \{ x : K(x) \ge |x| \}$. $L_K$, the language of incompressible strings is infinite.
• Theorem. The language $L_K$ is undecidable.
• Proof. Suppose $L_K$ is decidable. Then consider the following TM M:
• On input an integer $n$, M scans through each string $x$ of length $n$ and outputs the lexicographically first string that belongs to $L_K$.
• Claim 2. Let $x_n$ be the string output by M on input $n$. Then $K(x_n) \le C + \log_2 n$. But $K(x_n) \ge n$. Contradiction for $n$ larger than some constant!
• Therefore, our assumption is false and $L_K$ is undecidable.