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 :
- Generate all programs, indexed with increasing length
- For each program, check if the program outputs x
- 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 !