4 ms·
Kolmogorov complexity as a measure of randomness / information content has problems in my opinion: http://www.forwardscattering.org/post/7 http://www.forwardsca
by Ono-Sendai 13y ago
Kolmogorov complexity as a measure of randomness / information content has problems in my opinion: http://www.forwardscattering.org/post/7 http://www.forwardscattering.org/post/7
- j2kun 13y agoI think your contention (if you're the author of this post) is misguided. In particular, the "languages" you define have the string hard coded in their definition, and are hence at least as long as the string you want to encode. In other words, your additive constant is not universal. The definition of Kolmogorov complexity is not with regard to whatever machine you want. You fix one and only one universal Turing machine U at the beginning, and then you measure the Kolmogorov complexity of a string using a different language with respect to U. Using your notation, K(x) is defined as K_U(x), and you can relate it to K_perl(x) by K_perl(x) + |perl interpreter written in U| = K_U(x). If you wanted to redefine all of Kolmogorov complexity using your L_{perl, i} language, you could do that just fine, but then it's your bad definition that makes the interpretation silly. Besides, if you pick an otherwise "random" string and single it out as being special, doesn't that intuitively make it no longer random?
- Ono-Sendai 13y agoThanks for the detailed reply, I'll ponder upon it and reply in a bit :)
- Ono-Sendai 13y agoHi, My overall point is that it matters which UTM you pick at the beginning.
- tromp 13y agoYour 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.