In An Introduction to Kolmogorov Complexity and Its Applications explaining the notion of additively optimal or universal it is written:

The key point is not that the universal description method does necessarily give the shortest description in each case, but that no other description method can improve on it infinitely often.

How is this meant? For example fix some description mechanism, like some programming language. For some program $P$ in that language write $P()$ for its output with no input, $P(u)$ if $u \in X^*$ is some input, $P(u,v)$ if we have inputs $u, v \in X^*$ and so on, and we always have $P(...) \in X^*$, i.e. the input-output is string-based(1). Let $U$ be an interpreter, written in that language for programs in that language, then it is universal and as $U(Q, u) = Q(u)$ we have $$ C_U(w) \le C_Q(w) + |Q| $$ for each program $Q$. Also let $P$ be a program that expects some natural number $n$ in binary encoding, and prints $0^n$. Then $$ C_P(0^n) = \lceil \log_2(n) \rceil $$ as this is the space needed to encode some number in binary. As the shortest program which prints $0^n$ is a program which just outputs this number hardcoded and does nothing else (for example let $Q_n$ be the program "print 0...0", suppose writing $0^n$ is not supported by that language) we have $$ C_U(0^n) = \lceil \log_2(n) \rceil + C $$ where the constant comes from all the stuff needed to set up this programm (like the print-statement in $Q_n$). Then for the infinitely many strings $0^n$ we have $$ C_P(0^n) < C_U(0^n) $$ despite that this difference is bounded by a constant the description method $P$ indeed improves over $U$ infinitely often, or have I overlooked something? Is this not possible, or have I misunderstood the statement?

(1) Just a remark: Each program gives rise to a family of functions $f_n : (X^*)^n \to X^*$, or a single function $f : (X^*)^* \to X^*$ if we interpret the Kleene-star as the set of all sequences/tupels. The arguments could be interpreted as "command line" arguments. For a program $P$ the Kolmogorov complexity is defined as $$ C_P(w) = \min\{ |u_1| + \ldots + |u_n| : P(u_1,\ldots, u_n) = w \} $$ with $\min\emptyset := \infty$.

  • $\begingroup$ You are right; the authors must only mean that the difference is bounded. $\endgroup$ – Carl Mummert Jul 23 '15 at 12:13

Your Answer

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

Browse other questions tagged or ask your own question.