3
$\begingroup$

I wish to compare compressors using strings with known Kolmogorov Complexity, but I haven't got the theoretical background and tools to understand how to do that. I'm just starting in this area and any pointer to papers/textbooks is highly appreciated.

I imagine that to "tune" the KC of a string with length $n$, one has to use some random source, otherwise the same program used to generate several strings could be used as the measure of complexity for those strings. I idealized a state machine with two states (A and B, starting state = A) and a transition probability $p$ that would produce the following strings with different complexities for different $p$:

p = 0.0:    AAAAAAAAAAAAAAAAAAAAAAAAAA... 
KC ~ 1:     = A * n

p = 0.1:    AAAAAABBBBBAAAAAAAAAAAABBB... 
KC ~ n/10?: = (A * 6) ++ (B * 5) ++ (A * 12) ++ ...

p = 0.5:    AABBABABBBBBBAAABBABBBABBBA...
KC = n?

p = 0.9:    ABABAABABABABABBABABABABAA... 
KC ~ n/10?: = (AB * 2) ++ A ++ (AB * 5) ++ B ++ (AB * 4) ++ ...

p = 1.0:    ABABABABABABAABABABABABABA...
KC ~ 1:     = AB * (n/2)

However, this look like more some measure of entropy than proper KC. Are they equivalent for randomized processes?

$\endgroup$
  • 1
    $\begingroup$ I'm failing to understand your question. Possibly related: loria.fr/~hoyrup/dimension.pdf. $\endgroup$ – Quinn Culver Jan 4 '14 at 20:56
  • $\begingroup$ Quinn Culver, the question is the title: fixing the length $n$ of the string, is there a process to produce a string with a desired Kolmogorov complexity (between 1 and $n$)? I'll take a look on your link, thanks. $\endgroup$ – Bruno Kim Jan 5 '14 at 0:14
  • $\begingroup$ Thanks for your input, Quinn Culver, zyx and Carl Mummert. Although I can't say I understood everything 100%, I'll keep studying. I hope to come back with some smarter questions later on. Tangent to the topic, I wrote a blog post about an interesting prefix-free code I saw in a paper while studying information distance. Hope you enjoy. $\endgroup$ – Bruno Kim Jan 8 '14 at 17:34
3
$\begingroup$

This is an attempt to answer the titular question "Is it possible to create a string with known Kolmogorov Complexity?" (as elaborated in the comments: "fixing the length n of the string, is there a process to produce a string with a desired Kolmogorov complexity (between 1 and n)?").

My experience with Kolmogorov complexity is rather limited, but I think can say something helpful here.

The Kolmogorov complexity of a string is defined relative to a fixed universal (prefix free) machine. Since for any string $\sigma$ there is a universal machine $U$ such that $K_{U}(\sigma)=1$, the question only makes sense if we assume a fixed background universal machine $U$.

With $U$ fixed, the answer is no in general. First, the answer is no for the trivial reason that, given $n$, there's no guarantee that $K_{U}(\sigma)=n$ for any $\sigma$ at all.

Second, even if $U$ has the property that for each $n$ there is a $\sigma$ such that $K_{U}(\sigma)=n$, the answer is still no because if you've seen that $U(\tau)=\sigma$, so that $K_{U}(\sigma)\leq |\tau|$, if there's even one string $\rho$ with length less than $\tau$ such that $U$ is still undefined on $\rho$, then you'll just have to wait to determine if $U(\rho)=\sigma$. The point here is that the Kolmogorov complexity function isn't computable, but rather only computably approximable from above.

All that being said, I'd guess there is a universal machine $U$ with a computable set of strings $\langle \sigma_{n} \rangle_{n\in \mathbb{N}}$ such that $K_{U}(\sigma_{n}) = n$. I'm not sure of this though, and hopefully someone else will chime in and confirm/refute this guess (as well as the other things I've said).

$\endgroup$
  • 1
    $\begingroup$ The answer to the final paragraph is no; the answer is sufficiently non-obvious that I wrote it as a separate answer. $\endgroup$ – Carl Mummert Jan 6 '14 at 20:26
  • $\begingroup$ Here is a proof in words, probably the same as @CarlMummert's ( I didn't understand the notation). Given a source of pairs (string, lower bound on string's Kolmogorov complexity), if the set of KC bounds attained is known to be infinite, then the source can be used as a black box to get a stricter source that on input $i$ gives a string of KC at least $i$. That is impossible to do with a computer program as the initial source since the result is a way of adding at least $i - \log_2(i) + C$ bits of KC in addition to what is in the input code for $i$, for arbitrarily large $i$. $\endgroup$ – zyx Jan 7 '14 at 2:57
  • $\begingroup$ In the context of binary strings, $1^n0$ is a string of $n$ 1s followed by a 0. @zyx $\endgroup$ – Carl Mummert Jan 7 '14 at 3:59
  • $\begingroup$ That was the only part I did understand! I was not sure what prefix free function means (vs prefix free codes in information theory), or the meaning of the second sentence in the proof, or why in the generalization you speak of $K(\sigma_i)=n_i$ rather than an inequality $K(\sigma_i) \geq n_i$ (since it is the nontrivial lower bound that causes the impossibility, whether or not the sequence $(i,n_i)$ is r.e.). But the two arguments must be essentially the same since your contradiction comes from the same inequality (with $2^N$ corresponding to $i$). @CarlMummert $\endgroup$ – zyx Jan 7 '14 at 9:39
  • $\begingroup$ A prefix free function has a prefix free domain. What is your definition of a universal prefix free function to define Kolmogorov complexity? I allude to another one in the note. You're right that I could use $\leq$ in the generalization, but there is no contradiction unless the sequence is r.e. @zyx $\endgroup$ – Carl Mummert Jan 7 '14 at 12:51
3
$\begingroup$

The short answer is "no".

Random sources of known entropy, if you can find such a thing, give strings with KC probably close to $n$, more exactly a probability distribution of KC sharply concentrated near $n$, but exact determination of which strings have the precise value of KC you are looking for will not be possible.

You cannot create at will a string with Kolmogorov complexity known to equal $n$, because KC refers to minimum-length description by arbitrarily powerful computer programs, and judging that a string has $KC$ at least $k$ very quickly (that is, for small $k$) exceeds the power of any reasoning system (such as axiomatized mathematics, human brains, or networks of human and computer brains that collaborate using heuristics and axiomatized mathematics). Upper bounds on $KC$ are "only" a matter of having unlimited memory and unlimited time, just find the right program and run it. It is the lower bounds that are the killer.

For very limited forms of compression, like RLL, and short enough texts, it is possible to search through the possible compressed descriptions and produce optimally compressed texts. I don't know if this is feasible for something even slightly complex, like Lempel-Ziv coding; intuitively, if there is an efficient method for testing if a string is optimally compressed, then the compression method is trivial.

What is done in practice (for benchmarking) is to fix a compressor or a set of compressors, and use the compressed length of a text as the measure of complexity.

$\endgroup$
2
$\begingroup$

Is it possible to create a string with known Kolmogorov Complexity?

There cannot be a universal computable prefix-free function $U$ with that property that there is an r.e. sequence $\sigma_n$ of strings with $K_U(\sigma_n) = n$ for all $n$. So, in that sense, we cannot produce the desired string effectively.

Proof: Consider a computable prefix-free function $f$ such that $f(1^n0) = \sigma_{2^n}$ for each $n$. Then by universality of $U$ there is a fixed $w$ such that, for all $n$, $U(w1^n0) = \sigma_{2^n}$. Choosing $N$ large enough, $|w1^N0| = |w| + N + 1 < 2^N$, so $K_U(\sigma_{2^N}) < 2^N$, contradiction.

This generalizes to show it is impossible to have an r.e. sequence of pairs $(\sigma_i, n_i)$ with $K_U(\sigma_i) = n_i$ such that the set of $n_i$ that appears in the sequence is unbounded.

It is possible for an r.e. sequence of strings to contain strings of arbitrarily high complexity - the sequence that just enumerates all the strings must have that property - but it is not possible to correctly guess (in an r.e. way) the exactly complexities of a sequence of strings with arbitrarily high complexities.

This idea is at the root of the Chaitin incompleteness theorem. The additional idea there is that if we have an effective theory of arithmetic, we can enumerate all the proofs of statements of the form "$K_U(\sigma) = n$" to form an r.e. sequence of pairs $(\sigma, n)$. Thus: either the system proves some statements of that form that are false, or there is an $M$ such that $n<M$ in every statement of that form that is provable in the system. This applies to any fixed effective axiomatic system that includes statements that can be interpreted as "$K_U(\sigma) = n$".

$\endgroup$
  • $\begingroup$ Note: I looked up the definition of universal p.c. function on the Wikipedia article at en.wikipedia.org/wiki/Chaitin%27s_constant but the argument goes through equally well with the definition I am more used to: there is a $C$ such that, for all $n$, $K_U(\sigma_n) < C + n + 1$. Then the same inequality with $\sigma_{2^n}$ will be violated as soon as $C + 1 + N < 2^N$. $\endgroup$ – Carl Mummert Jan 6 '14 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.