4
$\begingroup$

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 !

$\endgroup$
3
  • $\begingroup$ It is a good statement of the problem, so clear that I suspect you have a pretty good idea of which of your three steps cannot be carried out in a deterministic fashion. $\endgroup$
    – hardmath
    Sep 25, 2018 at 15:28
  • 1
    $\begingroup$ The Wikipedia article on Kolmogorov complexity has a section that both explains why your algorithm won't work and sketches a proof why the Kolmogorov complexity is uncomputable. $\endgroup$ Sep 25, 2018 at 16:20
  • $\begingroup$ I got the proof and it is convincing, but I had troubles to find the close link between uncomputability and the halting problem, which is now obvious - especially with the formulation of point 2 $\endgroup$
    – Benichon
    Sep 26, 2018 at 13:27

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Do you have a reference for the reduction from the halting problem? I can't imagine how one would start using a Kolmogorov oracle to determine halting. (This assumes that we just have an oracle that computes Kolmogorov complexity relative to one fixed programming language. If we had a "universal" Kolmogorov oracle that we give both a universal machine and an output and it gives us the smallest input that produces this output, then there would be more to work with). $\endgroup$ Sep 25, 2018 at 19:00
  • $\begingroup$ Hello, I didn't know this "reduction" stuff but I've found some examples : nearly42.org/cstheory/halting_to_kolmogorov and here are 2 other exemples : www.nearly42.org/vdisk/articles/Program-size_Complexity_Computes_the_Halting_Problem.pdf $\endgroup$
    – Benichon
    Sep 26, 2018 at 13:22
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ True, I didn't see the link to the halting problem initially thanks ! $\endgroup$
    – Benichon
    Sep 26, 2018 at 13:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .