# Where does the "intuitive" understanding of Kolmogorov complexity fails

Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example on wikipedia.

So to give this more formal meaning, define $$K'(x) := |f| + |a_1| + \ldots |a_k|$$ where $f(s_1, s_2,\ldots, s_k)$ is some function with $k$ arguments in some specific programming language (like C++ for example).

How does this definition relates to Kolmogorov complexity? I mean this could not be the same, as with this definition we have $$K'(xy) \le K'(x) + K'(y) + C$$ with some constant $C$. For if $f(a_1, \ldots, a_k) = x$ and $g(b_1,\ldots, b_l) = y$ are functions to compute $x$ and $y$, then

h() {
return concat(f(a1, ..., ak), g(b1,...,bl));
}

would be a function to compute $xy$ of complexity $|f| + |a1| + \ldots + |ak| + |g| + |b1| + \ldots |bl| + C$, where $C$ represents the bits needed to declare $h$, the parentheses, the return statement and to call concat (string concatentation function).

Hence $K'(xy) \le K'(x) + K'(y) + C$.

But as is well-know for the usual Kolmogorov complexity we do not have such an subadditivity?

EDIT: This will also work if we just allow functions with a single parameter.

• It seems to me that if one defines $K(x)$ to be the size (i.e., length under some standard encoding, or perhaps even just number of states) of the smallest Turing machine which ignores its input, prints $x$ and halts -- then we do get a sub-additive notion? Apr 20, 2017 at 11:14
• @Aryeh Yes, but informally Kolmogorov complexity is defined as the shortest program to produce the string. But paradoxically even if we allow arguments (as above) we can built up a constant function (description) without the logarithmic term and get subadditivity, but this should not be possible... Apr 20, 2017 at 11:22
• @Aryeh Kolmogorov complexity measures the size of the smallest "program" for computing a given string. You cannot use the number of states in a machine to emulate this. Apr 20, 2017 at 11:29
• Oh I see -- the issue is that the number of states is const * description length of the TM, while we need const + ? Apr 20, 2017 at 11:36
• @Aryeh The issue is that there are too many Turing machines with the same number of states, and in particular, more than $2^n$ Turing machines on $n$ states. The actual number is super-exponential, $n^{\Theta(n)}$. Apr 20, 2017 at 11:42

• So if your encoding is not self-delimiting, how do you know where the program for $f$ ends and the program for $g$ begins? Apr 21, 2017 at 0:26
• @JoshuaGrochow What if we allow alphabets $X$ with $|X| > 2$ and have a special separting symbol like '#' in the inputs for a universal TM, then the codes themselves do not need to be self-delimiting, but nevertheless if we code them in an input separeted by '#' then we do not need additional overhead? Apr 24, 2017 at 14:18