Kolmogorov Complexity Lays Bare the Soul
9Zack_M_Davis
7Vladimir_Nesov
3TAG
3Viliam
3jakej
3Viliam
2quiet_NaN
1jakej
New Comment
Kolmogorov complexity has the counterintuitive property that an ensemble can be simpler than any one of its members. The shortest description of your soul isn't going to directly specify your soul; rather, it's going to be a description of our physical universe plus an "address" that points to you.
Quantum nondeterminism is going to make an address not much better than compressing the local content directly, searching for the thing rather than at a location. And to the extent laws of physics follow from the local content anyway (my mind holds memories of observing the world and physics textbooks), additionally specifying them does nothing. So unclear if salience of laws of physics in shortest descriptions is correct.
1Kolmogorov complexity has the counterintuitive property that an ensemble can be simpler than any one of its members
Yes but that's usually when the ensemble is infinite.
It is also completely unique, being the shortest possible string. It is so lean that not a single redundant detail remains - otherwise, it would not be the shortest string.
I don't think this is necessarily true. (Though I am not sure about it.) I imagine there could be two different compression strategies that both happen to produce a result of the same length, but cannot be merged.
To use your example, "AAABB" can be compressed to either "3A2B" or "3ABB", both containing 4 characters. Knowing that "2B" and "BB" represent the same thing doesn't allow you to exploit this "redundancy" to further reduce it to one character.
Also, some parts of my body and mind are more important than others -- the exact shape of all my hairs at this moment is a lot of data (not easy to compress, because there is a lot of randomness involved), and in a second the shape will be different anyway, and even if you cut my hair short it would still be "me" (at least I do not experience existential horror whenever I get a haircut). Also not sure if gut flora should be included.
I guess my point is that even relatively useless things can require many bits of information and you actually don't need them, some lossy compression would suffice, but if you overdo it, you get The Fly.
I imagine there could be two different compression strategies that both happen to produce a result of the same length, but cannot be merged.
I think this is correct, but I think of this as being similar to chirality - multiple symmetric versions of the same essential information. I think it also probably depends on the description language you use, so maybe in one language something might have multiple versions, but in another it wouldn't?
Yes, if there is no deep underlying reason why the two minimal descriptions should be same, and it "just happened", I would assume that with slightly different description language it would not happen.
Even the "3A2B" vs "3ABB" example would stop working if encoding a number used a different number of bits than encoding a character.
First off, the most important practical property of the Kolmogorov complexity is that it is not computable. This means that there is no general algorithm to determine what is the shortest computer program to generate a given output. (The crux is that you can not run all programs below a certain length to see if any of them will generate that output, because some of these programs will run forever, while others might run for an non-computable long time and eventually print that output and terminate.)
This is the reason why we have myriads of heuristic compression algorithms instead of just using Kolmogorov compression, which would yield the best possible results.
It is also completely unique, being the shortest possible string.
No, there can be more than one such string.
Even leaving issues of quantum physics aside, macroscopic physical objects like humans are unlikely to be very compressible (information-wise, that is). The author might feel that the number of lead atoms in their 36 molar tooth is not part of their Kolmogorov string, but I would argue that is is certainly part of a complete description.
Humans are not the product of running some simple starting conditions in some deterministic cellular automaton, but shaped by a chaotic environment full of probabilistic interactions. Mess not math, if you will.
In practice, that fine level of detail is not actually what I care about. Just like I listen to lossy compressed music, I would be fine with being uploaded into a somewhat lossy representation of myself where I don't have any lead atoms in my teeth.
Even leaving issues of quantum physics aside, macroscopic physical objects like humans are unlikely to be very compressible (information-wise, that is). The author might feel that the number of lead atoms in their 36 molar tooth is not part of their Kolmogorov string, but I would argue that is is certainly part of a complete description.
I don't know, just how compressible are we? I agree that the lead in my 36 molar is a part of my description, but anomalies such as these are always going to be the hardest part of compression since noise is not compressible. So maybe a complete description would look more like "all of the usual teeth, with xyz lead anomalies".
In practice, that fine level of detail is not actually what I care about. Just like I listen to lossy compressed music, I would be fine with being uploaded into a somewhat lossy representation of myself where I don't have any lead atoms in my teeth.
The "noise" of lead atoms in your teeth are among the least important bits in your Kolmogorov string, and would be the first to be dropped if you decided to allow a lossy representation. This reminds me of overfitting actually. The first thing a model tries to learn are the actual useful bits, and then later on when you train too long it starts to memorize the random noise in the dataset.
