3 ms·
I 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 definiti
by j2kun 13y ago
I 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.