0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    May 24 at 5:30

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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 $\endgroup$
    – Sam
    May 24 at 15:06
  • 1
    $\begingroup$ @Sam, see edited answer. $\endgroup$
    – D.W. ♦
    May 24 at 15:41
  • $\begingroup$ thanks for the updated reply. Could you briefly explain why Turing machine is a programming language? I thought we are talking about a specific type of practical programming language (e.g., C, C++, etc.) and it is possible that some of them interpret the input differently. Or could you suggest some reference materials? $\endgroup$
    – Sam
    May 24 at 19:13
  • $\begingroup$ @Sam, you can define a version of Kolmogorov complexity with respect to any fixed programming language if you wish. I strongly urge you to read a textbook with a careful exposition of this. Interactive back-and-forth and follow-up questions are not part of the goal of this site. $\endgroup$
    – D.W. ♦
    May 25 at 0:07
  • 1
    $\begingroup$ @Sam, Cover & Thomas, Elements of Information Theory has a chapter on it. Lin & Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications might be good too, but I don't have experience with it. An online websearch turns up lecture notes from courses. I imagine you can find more if you spend some time on research. $\endgroup$
    – D.W. ♦
    May 25 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.