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 \{ |<M>|+|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.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s