Uncomputability of Kolmogorov complexity

Question

I have read different proofs of Kolmogorov Complexity Uncomputability but I fail to understand why the example below does not work. Certainly there is something important that I don't get.

Could you please help me understand why the following argument is wrong ?

"The Komogorov complexity of a string is the number of bits of the shortest program that can print the string."

So for any string x the shortest program that can print x exists. We want to compute its length.

Consider the following program :

1. Generate all programs, indexed with increasing length
2. For each program, check if the program outputs x
3. As soon as we find a program that outputs x, return the length of this program.

By construction we will find the shortest length possible for a program outputing x, which is the Kolmogorov Complexity if x.

I have lots of troubles finding why this fails to provide a way to compute Kolmogorov Complexity of any x.

Thanks a lot for your help !

Answer 1

Your point (2) is hiding a fundamental assumption:

$(*)\quad$ Given a program $\pi$ and a string $s$, we can computably tell whether $\pi$ outputs $\sigma$.

The reason this is problematic is that some programs never halt at all. So given a program $\pi$, if we just want to wait until it outputs a string, and then check whether that string is $\sigma$, we'll potentially never resolve this step. E.g. maybe the $0$th program never halts; even if the $1$st program does halt and output $\sigma$, in order to be certain that $1$ is the least index of a program outputting $\sigma$ we need to somehow convince ourselves that the $0$th program will never halt, and we can't do this simply by running it for a long time.

So in order to perform your step (2), we need to be able to tell when a program is never going to halt (so we can throw those bad programs away and concentrate on the non-silly ones). But this is not something we can computably do.

---

Of course, this doesn't prove that Kolmogorov complexity is undecidable (precisely: that the function sending each string to its Kolmogorov complexity is not computable). But it suggests a line of attack: try to show that the above obstacle is essential. That is, we want to show that if we could compute the Kolmogorov complexity of an arbitrary string we could use this to solve the Halting Problem (put another way, we want to reduce the Halting Problem to the Kolmogorov complexity problem). This in fact works, although it takes a bit of thought.

Answer 2

Your program gets stuck on step 2, waiting for the child program to terminate