Kolmogorov Undecidability and Godel Incompleteness

PDF of Prof. Santosh’s handwritten notes is here.

  • 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 \{ |\langle M\rangle|+|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.

 

Godel’s Incompleteness Theorem

Any ‘sufficiently powerful’ axiomatic system is either:

1. Inconsistent: \exists a statement that is provable and so is its negation

2. Incomplete: \exists a true statement that is not provable within the system

An axiomatic system is ‘sufficiently powerful’ if it can encode Turing Machines.

Proof

Any candidate proof P of a statement S can be checked within the system.

We assume that the statement HALT(M,x) which stands for “TM M halts on input x” can be expressed in the system.

Assumptions:

  1. If M halts on x, there is a proof of HALT(M,x)
  2. If M does not halt on x, there is a proof of \overline{HALT}(M,x)

Consider the following TM D:

TM D on input (\langle M\rangle,x)

  • k = 1
  •  While(True)
    • Enumerate every proof P of length k (there are finitely many):
      • If P is a proof of HALT(M,x) : ACCEPT
      • If P is a proof of \overline{HALT}(M,x) : REJECT
    • k = k+1

The TM D will always halt since there is either a proof of HALT(M,x) or a proof of \overline{HALT}(M,x) and the TM will find it in finite steps. Thus, the TM D decides the language L_{HALT} = \{(\langle M\rangle, x): M \text{ is a TM which halts on input }x \}. From previous lectures, we know that L_{HALT} is undecidable. This leads to a contradiction.

If we assume our system is consistent, at least one of our assumptions is incorrect. If either assumption is incorrect, we have a true statement that is unprovable in the system.

Alternative proof via Kolmogorov complexity

Recall that the Kolmogorov complexity for a string x is defined as:
K(x) = \min \{ |\langle M \rangle| + |y| : M on input y produces x \}

Also, we proved the following theorem: L_k = \{x : K(x) \ge |x|\} is undecidable

Take any axiomatic system where the statement “K(x) \ge n” can be expressed. Also, assume that it is possible to verify if a string P is a proof of a statement S in the system.

Theorem: there exists true statements that are unprovable within any consistent system. More concretely, \exists n_0, \forall n \ge n_0, \exists x, the statement K(x) \ge n is true but cannot be proved.

Proof:

Suppose \forall x, \forall n if K(x) \ge n is true, it has a proof in the system. We also assumed that any candidate proof P of a statement S can be verified in the system. This gives us the ability to find incompressible strings.

Define TM M on input n:

  • enumerate pairs of integers (s,p)
    • for each pair (s,p), enumerate strings x of length s and proofs P of length p
    • If P is a proof of the statement K(x) \ge n:
    • Output x and halt

If x, P exist for n, the TM M will output x for which n \le K(x) \le C + \log{n}, where C denotes the size of \langle M \rangle.

Thus, \exists n_0 s.t. \forall n \ge n_0, \exists x, the statement K(x) \ge n has no proof!

This is particularly striking since it is easy to produce strings x for which K(x) \ge n. If we pick a random string of length n+1, then with probability \dfrac{1}{2}, K(x) \ge n.

Advertisements