# 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$.