2
$\begingroup$

Is it true that for all strings of a given length at least one has its Kolmogorov complexity equal to its length ?

Is there a proof if the answer is in affirmative? (For any alphabet with more than symbol)

$\endgroup$
1
$\begingroup$

Kolmogorov complexity is defined with respect to some fixed universal (additively optimal) description mechanism. So in general the answer depends on the description mechanism. For example if you choose some known programming language (like C, Java and so on) and consider strings of length one, then each program to print them needs additional commands to set them up (like the entry procedure and the print commands in the case of Java and C) and so has Kolmogorov complexity $> 1$. As in general using regularities the description length could be shorter, for some $n$ this might be possible. For example use the C-programming language as universal description mechanism, then

for(int i=1;i<32;++i)printf("1")

is a program of length 32 (ignoring the main-part and so on if interpreted as a C-program), and it prints exactly a string of length 32. If this is the shortest possible C-program then its Kolmogorov complexity would be 32. But this is with respect to the C programming language, for another description mechanism this might be different.

EDIT: Regarding your comment I guess I misunderstood your question slighty or what you have in mind, so let me add some explanations regarding my example and your comment. As you said if we fix some universal computing mechanism (you can think of this as fixing some general purpose programming language, like C), and we define $$ K(w) := \mbox{Length of shortest program to print }w\mbox{ in this computing mechanism.} $$ Then of course you can always find $w$ such that $K(w) \ge |w|$, a proof is based on the pigeonhole principle and some counting, as you said: For each $n$ there are just $1 + 2^1 + 2^2 + \ldots + 2^{n-1} = 2^n - 1$ strings of length less than $n$ (in the sum I counted the ones of length zero, length one, length two and so on up to $n-1$), but we have $2^n$ string of length $n$, therefore there must be some string which has a description not shorther then its own length (as by pigeonhole principle otherwise some string would have two description's, which is not possible).

Note that with regard to the wording of your question this does not imply that we have $K(w) = |w|$ (it might be, but does not have to be), just $K(w) \ge |w|$.

Also regarding my initial answer. There I showed that sometimes you could find such strings that $K(w) = |w|$ for some special computing mechanism (do not know if your question was meant with some fixed computing mechanism beforehand in your mind, so that you do no allow to vary that). But in general if you fixe some arbitrary computing mechanism this might not be possible, just that $K(w) \ge |w|$ is guarranted as shown above. Such string by the way are called random (or $0$-random to be precise). But with this interpretation my example might seem a little bit odd, as the string $1^{32}$ is far from being random, but by construction for the universal computing mechanism $C$ programming langugae we need exactly $32$ symbols to describe it (neglecting the main-procedure and so on). What I used here is some artefact of the special computing mechanism, here setting up loops and so on, but such things enter the complexity description in some "asymptotical neglectible way" (maybe some expert can say this better...). For example consider a program mechanism which allows me to write $\mbox{print } 1^{32}$, suddenly the decription is much shorter (note that to print $1^n$ we also need to code $n$, i.e. how many times the loop should run in the above example, and this takes $\log n$ space, so in general we have $K(1^n) \le c_1 \cdot \log n + c_2$, where the constants come from other code, setting up loops, separating the input for universal machine and so on).

Okay, lastly I give you a computing mechanism for which we do not have $K(w) = |w|$ for no $w$. Let me write this in more mathematical terme of partial recursive functions, i.e. for some partial recursive function $\varphi : X^* \to X^*$ we define $K_{\varphi}(w) := \min\{ \pi : \varphi(\pi) = w \}$ the Kolmogoroff complexity w.r.t. $\varphi$. For $|u| = n > 0$ set $\varphi(u_1 u_2 \cdots u_n) := u_2 \cdots u_n$ and $\varphi(\varepsilon) := 1$ (think of this as some ridiculous copy mechanism which forgets about the first symbol for each non-empty word), then we have $K_{\varphi}(1) = 0$ and $K_{\varphi}(w) = |w| + 1$ for every other word. Of course, the above example is really artificial and the computing mechanism is not universal (it cannot "simulate" other mechanism). For universal mechanism this might be possible too, but then you have to play around with the coding constants and the codings (i.e. how to describe the partial recursive functions), which might get quite messy, but let me know if you are interested, maybe I can outline a construction.

$\endgroup$
  • $\begingroup$ But there will be strings of any arbitrary length which have complexity equal or MORE than their lengths regardless of the description mechanism : Pigeonhole principle! $\endgroup$ – ARi Jul 30 '15 at 16:18
  • 1
    $\begingroup$ Okay, that was the Theorem you had in mind, so maybe you have some fixed computing mechanism in advance. This makes the discussion a littlbe bit more abstract, and is nearer at the notion of "inherent complexity" of some object. I expanded my answer, taking into account what is possible if some computing mechanism is fixed (which is often done when discussing Kolmogorov complexity). Hoping all your question are answered now. $\endgroup$ – StefanH Jul 31 '15 at 12:05

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.