Approximating the Kolmogorov complexity

Question

I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors (identify how each author writes some text and group documents by their similarity).

In that case, data compressors were used to approximate the Kolmogorov complexity, since the data compressor could be used as a Turing Machine.

Besides data compression and programming languages (in which you would write some kind of compressor), what else could be used to approximate the Kolmogorov complexity? Are there any other approaches that could be used?

Answer 1

I guess one possible answer to your question is this: Take a pseudorandom number generator $G$. Try to chose a generator which has some powerful attacks against it: a random number generator attack for $G$ is (for our purposes), an algorithm $A$ which, when given an imput string $s$, determines a seed $A(s)$, such that $G(A(s))=s$. Then approximate the KC of $s$:

input: s
Compute A(s);
if |A(s)| + |G| > |s| output: |s|
otherwise output: |A(s)| + |G|

Where $|G|$ is the length of the program that computes $G(s)$ (often quite short, as for linear generators).

Note that in practice, random number generator attacks are not as described: they may fail or produce incomplete results. In that case, you may adapt the algorithm so that it returns $|s|$ when the result of the attack is unsatisfactory. The same remark goes for compression algorithms.

The caveat to this approach as opposed to compression algorithms is that compression algorithms are in general much more suited to computing KC as they are tailored to work on any string, whereas an attack can work only if $s$ happens to be in the image of $G$ (very unlikely).

Answer 2

Any probability distribution. If you have a computable probability distribution that gives your data probability $p(x)$, then by the Kraft inequality, there's a computable compressor that compresses it in $-\log p(x)$ bits (round up if you object to fractional bits). This means pretty much any generative machine learning algorithm can be used.

This is why Kolmogorov complexity is so interesting, not because it's the ultimate compression algorithm (who cares about compression anyway), but because it's the ultimate learning algorithm. Compression and learning are basically the same thing: finding patterns in your data. The statistical framework built on this idea is called Minimum Description Length, and it was directly inspired by Kolmogorov complexity.

See also this question over at the cstheory StackExchange.

Answer 3

grammar coding is a less-frequently used version of a compression algorithm and can be taken as a "rough" estimate of Kolmogorov complexity. grammar coding is not as commonly used as a compression algorithm as other more common approaches maybe mainly because it doesnt improve much on compression from eg Lempel-Ziv on text based-corpuses, but it may do well on other kinds of data. the idea is to "compress" a string using grammar rules. a grammar derivation can result in a DAG (vs a less complex tree) so there is substantial representational complexity possible.

another option is to find smallest/minimal circuits representing a string but this is known to have very high complexity of computation and could succeed only on small strings.

generally the closer any approximation comes to calculating $K(x)$, the more intractable it is.

in an informal sense, generally any "approximation" of $K(x)$ must also be a "compression algorithm".

there are also other compression algorithm methods besides Lempel-Ziv "run length encoding" type approaches, for example vector algebra and the SVD can be used as a compression algorithm. also Fourier transforms are frequently used to compress images eg in JPG standard.