PM5388: Concerning Kolmogorov distance

Also see Wikipedia article on "mutual information", which is connected to this topic.

Firstly, let us define a universe as a finite set of points in a space X^n, for some finite integral dimensionality n, where X is some countable field, such as the rationals, the algebraic reals, the computable reals, or the first-order definable reals.

Now, every such universe can be given a straightforward description, which is a string listing every point in that universe in order. The precise encoding shall vary, including depending on the field in question - but the point is that every universe can be given a unique description which is to say straightforward, which will be a finite string in some finite alphabet.

The Kolmogorov complexity of a string is the length of the shortest program for some Turing-equivalent computer which will produce that string as output. The description of a universe by such a 'straightforward' string will obviously be highly-compressible; thus the shortest program which produces that universe will be much shorter than the straightforward description (at least, for the kind of universe we are in). So, every universe has a Kolmogorov complexity.

We can define the Kolmogorov distance between two strings a,b as follows: the length of the shortest program (for a Turing-equivalent computer) that given string a as input will produce string b as output. Kolmogorov distance is independent of Kolmogorov complexity; two strings may have very high Kolmogorov complexity, yet there may be a very simple transformation between them. The Kolmogorov complexity of a string can be defined as the Kolmogorov distance between it and the empty string. We can explore a few variations of this idea: unidirectional Kolmogorov distance (the distance from a to b may differ from that from b to a, since transforming a into b may be far simpler than trnasforming b into a); bidirectional Kolmogorov distance (the shortest program which given one string will produce the other, so given a as input will output b and given b as input will output a), etc. One wonders whether one could define a 'Kolmogorov metric' on the space of strings - a metric must have four properties: non-negativity, identity of indiscernibles, symmetry and subadditivity/triangle inequality. Non-negativity clearly holds (a program cannot have a negative length); identity of indiscernibles generally doesn't, although we can make it hold by choosing a language in which the empty string is a program which copies input to output then halts - or else just modify our definition to fix the distance between a string and itself as zero (even if a program to implement the identity function would be of non-zero length; symmetry is not going to hold for the unidirectional Kolmogorov distance, but would hold for the bidirectional Kolmogorov distance. That leaves the triangle inequality - it is hard to say whether it holds, but I would guess it probably doesn't. Although, even if it doesn't hold, maybe we can finesse the idea of Kolmogorov distance until it does. (Just as, bidirectional Kolmogorov distance is getting closer to being a metric than unidirectional Kolmogorov distance.)

So, maybe we can define a metric space, or at least a semi-metric space, based on Kolmogorov distance.

Now, consider two strings A and B. A trivial program to implement output B given A is to output B unconditionally (for all inputs). So, the unidirectional Kolmogorov distance from A to B is at most the Kolmogorov complexity of B. However, if A and B are somehow related, it might be significantly less than B. For bidirectional Kolmogorv distance, the definition is given A as input our program must output B, given B as input our program must output A. (How it behaves for other inputs is undefined.) Now, the most trivial program would contain encoded in itself straightforwardly the strings A and B, compare its input to each string to see if it gets a match, when it matches one string it outputs the other. (We don't care what it does for other inputs.) The length of such a program is going to be the length of A plus the length of B plus a constant factor. So, we can define an upper-bound on bidirectional Kolmogorov distance in terms of the length of the respective strings.

If we have programs p(A) and p(B) which are the Kolmogorov compression of A and B respectively, we could simulate execution of p(A) and p(B), interleave execution steps from each (i.e. execute both simultaneously in a round-robin fashion), comparing the output of each to the input, when we have confirmed a match of our input to one of them, we start outputting the result of the other. The length of such a program would equal the length of p(A) and the length of p(B) plus a constant factor. So we can also define an upper-bound on bidirectional Kolmogorov distance between two strings in terms of the Kolmogorov complexity of each of them.

In Maratreanism, the basic idea is that we start with a universe in which there exists unfulfilled true desire. For each of those unfulfilled true desires, there will be other possible universes in which those desires would be fulfilled. Maratrea chooses one of them to create in order that that desire be fulfilled in that universe; but how does she choose which universe to create? She chooses to create the nearest universe to the desire-origination universe. How do we define "nearness" between universes? The framework of Kolmogorov distance enables us to provide such a definition.

However, how can she do this, when Kolmogorov distance is an uncomputable function? She does not herself perform the necessary computations; she delegates to a being known as the many-bejewelled god. The many-bejewelled god is a spirit, but not a personal spirit; in other words, a soulless spirit (we may suggest, a quasipersonal spirit). The many-bejewelled god effectively has the power to perform Turing-equivalent computation. And yet, Turing-equivalent computation is insufficient to determine Kolmogorov distance. There is thus another entity, the far-beyond god, which is likewise a soulless spirit, which functions as an oracle for the halting problem. The many-bejewelled god prays to the far-beyond god, and receives an answer to his prayer. Thus, the many-bejewelled god can calculate Kolmogorov distance on behalf of Maratrea; thus, through his services, she can find the nearest universe to the desire-origination universe of a true desire which fulfills that true desire.

Comments