4 ms·

Kolmogorov complexity is not computable in general, but it is decidable for a substantial subset of programs.

moyix 10y ago
Really? Do you have an example of a substantial set of programs where that holds? I don't see a priori how it could work unless you can do exhaustive search over the space of all programs and determine if they halt and return the right answer.
- yorwba 10y ago
  The hard part here is not finding a set of programs that always halt (primitive recursive functions can compute anything you'd ever want to run on large inputs), but proving that they are correct (I'm pretty sure equivalence of primitive recursive functions is undecidable). Edit: but if someone gives you the primitive recursive Kolmogorov complexity of a program, you can check it by running all shorter programs on all inputs until you found a counterexample for each of them. So it is semi-decidable. Edit to edit: This would even work for the general Turing-machine definition of Kolmogorov complexity.
  - vog 10y ago
    > The hard part here is not finding a set of programs that always halt [...], but proving that they are correct (I'm pretty sure equivalence of primitive recursive functions is undecidable). This may be true, but: If you use primitive recursive functions (instead of turing complete) because of practicality, with the same reasoning you can cap the inputs at some insanely large number. Then, these functions still "can compute anything you'd ever want to run on large inputs". In that setting, equivalence is decidable, because you can simply run both functions over the finite set of all possible inputs.
- slaymaker1907 10y ago
  Formally, there are quite a few which are quite simple to show. For instance, for the string 'a', the shortest python problem which can produce this string is obviously print('a') since 'a' has only one character. Additionally, if you limit your language to a recursive language, you can compute complexity (which is no longer Komnogorov) directly. Simply begin enumerating all programs in order of length and then run them checking the output to see if it is that string. While this is by no means efficient, it works for recursive functions since they must halt. For Komogorov complexity, there isn't really a notion of inputs, merely that some particular string should be produced as output. For recursively enumerable (i.e. Turing complete) languages, the former method will not work because a program might run forever.
  - mafribe 10y ago
    Interesting. This way you get an upper bound on the Kolmogorov complexity of any given string. Do you know how good this approximation is in the worst/best/average case? This sounds like the kind of question that would have been investigated.

moyix 10y ago

Really? Do you have an example of a substantial set of programs where that holds? I don't see a priori how it could work unless you can do exhaustive search over the space of all programs and determine if they halt and return the right answer.

yorwba 10y ago
The hard part here is not finding a set of programs that always halt (primitive recursive functions can compute anything you'd ever want to run on large inputs), but proving that they are correct (I'm pretty sure equivalence of primitive recursive functions is undecidable). Edit: but if someone gives you the primitive recursive Kolmogorov complexity of a program, you can check it by running all shorter programs on all inputs until you found a counterexample for each of them. So it is semi-decidable. Edit to edit: This would even work for the general Turing-machine definition of Kolmogorov complexity.
- vog 10y ago
  > The hard part here is not finding a set of programs that always halt [...], but proving that they are correct (I'm pretty sure equivalence of primitive recursive functions is undecidable). This may be true, but: If you use primitive recursive functions (instead of turing complete) because of practicality, with the same reasoning you can cap the inputs at some insanely large number. Then, these functions still "can compute anything you'd ever want to run on large inputs". In that setting, equivalence is decidable, because you can simply run both functions over the finite set of all possible inputs.
slaymaker1907 10y ago
Formally, there are quite a few which are quite simple to show. For instance, for the string 'a', the shortest python problem which can produce this string is obviously print('a') since 'a' has only one character. Additionally, if you limit your language to a recursive language, you can compute complexity (which is no longer Komnogorov) directly. Simply begin enumerating all programs in order of length and then run them checking the output to see if it is that string. While this is by no means efficient, it works for recursive functions since they must halt. For Komogorov complexity, there isn't really a notion of inputs, merely that some particular string should be produced as output. For recursively enumerable (i.e. Turing complete) languages, the former method will not work because a program might run forever.
- mafribe 10y ago
  Interesting. This way you get an upper bound on the Kolmogorov complexity of any given string. Do you know how good this approximation is in the worst/best/average case? This sounds like the kind of question that would have been investigated.