# On proving the uncomputability of Kolmogorov complexity by contradiction

I have seen a proof by contradiction for the uncomputability of Kolmogorov complexity. The idea the basically the same as in the proof for halting problem (i.e., there are cases that lead to Berry paradox example). However, I would argue that since there are infinitely possible ways to interpret a given string, this fact already shows that in the worst case, you can't even iterate through any string, let alone finding the equivalent shortest string for a given string. Is there anything wrong to my reasoning?

• What is your question? I don't see a question here. We are a question-and-answer site, so we require you to articulate a specific question.
– D.W.
May 24 at 5:30

Kolmogorov complexity doesn't say anything about "interpret"ing a string or finding the equivalent shortest string for a given string, so your argument is not relevant. I don't know what it means to say that one can or cannot iterate through any string.

Kolmogorov complexity has a precise mathematical definition, as does the notion of computability. Arguments in informal English language can often lead one astray, as they might not correspond to the actual mathematical concepts.

Your comment clarifies that you're concerned that there could be an infinite number of programming languages that could be used. That's not correct. With Kolmogorov complexity, we first fix a programming language -- typically, Turing machines.

I suggest finding a textbook or lecture notes that covers this. Wikipedia is probably not sufficient as a resource, as there are important details that aren't listed there.

• My issue is not necessarily on the formal proof of Kolmogorov complexity, but the if isValidProgram(p) and evaluate(p) == s condition in the native example given in Wikipedia (see link above). On the statement 'However this will not work because ... all of these programs by testing them in some way before executing them due to the non-computability of the halting problem', I am trying to say you don't even need to look at evaluate(p) == s, because isValidProgram(p) already cannot be evaluated because there are potentially infinite different programming languages out there
– Sam
May 24 at 15:06