Re:Kolmogorov Complexity and Compression Distance
by rhelz on Sunday March 31, 2024 @03:21PM
(#39887211)
Well, here's why it's not that simple....I can make any number N have a kolmogorov complexity number equal to 1--if the Turing machine has N+1 symbols :-) I just express the number in base N. (which will bet "10" for any base :-)
It true that we typically limit ourselves to binary when we are proving theorems, etc in Kolmogorov complexity. You can prove that for any two turing machines U and V, KU(X) <= KV(X) + O(1).....but this relies on the fact that there is an O(1)-sized program which lets U emulate V, and V emulate U.
And that is only true if U and V share the same symbol set. If they don't, then the kolmogorov complexity of the two machines can be made arbitrarily different from each other, just by changing the symbol set.
It true that we typically limit ourselves to binary when we are proving theorems, etc in Kolmogorov complexity. You can prove that for any two turing machines U and V, KU(X) <= KV(X) + O(1).....but this relies on the fact that there is an O(1)-sized program which lets U emulate V, and V emulate U.
And that is only true if U and V share the same symbol set. If they don't, then the kolmogorov complexity of the two machines can be made arbitrarily different from each other, just by changing the symbol set.