17 ms·
Your claimed definition: "The overall Kolmogorov complexity of a string is thus defined as K(x)=|p| where p is the shortest program string for language L such
by tromp 13y ago
Your claimed definition:
"The overall Kolmogorov complexity of a string is thus defined as K(x)=|p| where p is the shortest program string for language L such that L(p)=x and we consider all programming languages."
is clearly wrong. You cannot take the minimum over all languages, or over all universal languages, because that leaves K() equal to a constant function.
You really need to fix L. I tried to define the simplest possible language on which to base Kolmogorov complexity and ended up with
http://en.wikipedia.org/wiki/Binary_lambda_calculus http://en.wikipedia.org/wiki/Binary_lambda_calculus
- Ono-Sendai 13y agoWell my contention is that K(x) is constant, in fact K(x) = 0. The problem with fixing L is that it 'biases' the complexity based on the language chosen.
- shasta 13y agoThat bias with a fixed L is present, but you already mentioned the answer in your article: the difference is bounded. Compare to the situation with algorithm complexity. We usually don't attempt to talk about the running time of merge sort by fixing a reference machine on which to do an instruction count. We instead introduce Big-Oh and agree to ignore the differences in constants.
- gwern 13y ago> We usually don't attempt to talk about the running time of merge sort by fixing a reference machine on which to do an instruction count. Unless you're Knuth!
- Ono-Sendai 13y agoThe difference is not really bounded in a meaningful way. The bound is large enough that the complexity can go to zero in some language.