Some Easy Theorems in Kolmogorov Theory Exposition by William Gasarch (gasarch@cs.umd.edu)
1 Introduction
Intuitively the string 00000000000000000000000000000000000000000000000000000000000000000000
is not random. Note that you could write a program of length O(log n) that print out 0n. Intuitively the string
01101000110000001110101010001100011010010010101001010110101010111110000 is random. The shortest program to print it out might just be
print(01101000110000001110101010001100011010010010101001010110101010111110000) which is of length roughly the length of the string.
With this in mind Kolmogorov defined the following notion of complexity.
Definition 1.1 The Kolmogorov complexity of a string x, denoted C(x), is the length of the short- est program that prints out x. (To make this formal you would need to define (1) define a model of computation such as Turing Machines, and (2) prove that the complexity only differs from a constant depending on which model you are using. We will not bother with that.)
Note 1.2 We often call algorithms that print out a string x a description of x. Lemma 1.3 For almost all n there is a string x ∈ {0, 1}n such that C(x) ≥ n.
Proof: Assume, by way of contradiction, that for all x ∈ {0, 1}n C(x) < n. Map each x ∈ {0, 1}n
to the program that prints it. Note that this map is 1-1. There are 2n elements in the domain and
n−1 2i = 2n − 1 in the range. Hence the map cannot be 1-1. Contradiction. i=0
2 Classic proof that C is Not Computable Theorem 2.1 C is not computable.
Proof:
Assume, by way of contradiction, that C is computable. Assume also that the program for C is of size s. Consider the following program (Where a is a constant to be named later.)
For each x ∈ Σas compute C(x). When you find an x such that C(x) ≥ as print out that x.
This program is of size s+lg(as)+O(1). Its output is a string of length as. Pick a large enough so that
s + lg(as) + O(1) < as.
But now the output is a string whose shortest description is of length as. Contradiction.
1
3 Easy Known Proof that C ≤T K Theorem 3.1 C ≤T K.
Proof:
1. 2.
3.
Input x. We want to know C(x).
For all Turing machines M of length ≤ |x| ask Does M(0) halt and output x? using the oracle
for HALT.
Output the length of the shortest M such that M(0) ↓= x
Main Point
4
The proof that C is undecidable is unusual in that we do not use HALT. That is, the proof is not a reduction. Note also that C ≤T HALT.
My students sometimes ask me Will there be a problem on the exam where we need to prove something is undeniable, but a reduction to HALT won’t work? which is a stupid way to ask the smart question: Is there a set A such that ∅