[Solved]: Approximating the Kolmogorov complexity

Problem Detail: 

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?

Asked By : woliveirajr

Answered By : cody

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3501