6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Aryeh Apr 20 '17 at 11:14
  • $\begingroup$ @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... $\endgroup$ – StefanH Apr 20 '17 at 11:22
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus Apr 20 '17 at 11:29
  • $\begingroup$ Oh I see -- the issue is that the number of states is const * description length of the TM, while we need const + ? $\endgroup$ – Aryeh Apr 20 '17 at 11:36
  • 1
    $\begingroup$ @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)}$. $\endgroup$ – Yuval Filmus Apr 20 '17 at 11:42
6
$\begingroup$

The issue in play here is whether you use a self-terminating encoding (like your C example) or not. If you use a self-terminating encoding, then the subadditivity property does hold. If you don't (as in the common definition), then you need to expend bits on delimiting encodings.

Self-terminating encodings have other advantages, and even though real programming languages are always self-terminating, the pioneers of Kolmogorov complexity (Solomonoff, Kolmogorov and Chaitin) defined their notion of complexity with respect to non-self-terminating encodings. The classic monograph of Li and Vitanyi treats both variants.

$\endgroup$
  • $\begingroup$ I am aware of self-delimiting encoding, and I know that we can get subadditivity there. And despite the fact that most programming languages are self-delimiting, this is not the point here! The point is that we can encode the parameters in the machines itself just with a constant overhead, and therefore get subadditivity. But this must break-down somewhere. You can do the same with some non-self-delimiting programming language, for example get rid of parentheses and formating and other ways to specify parameters to have the same paradox in the end. $\endgroup$ – StefanH Apr 20 '17 at 11:59
  • 9
    $\begingroup$ So if your encoding is not self-delimiting, how do you know where the program for $f$ ends and the program for $g$ begins? $\endgroup$ – Sasho Nikolov Apr 21 '17 at 0:26
  • 3
    $\begingroup$ @StefanH: In other words, your intuition here breaks down because your intuition is based on programming languages people actually use, all of which are self-delimiting. In a general acceptable numbering, you can't "encode the parameters in the machines itself with just a constant overhead." $\endgroup$ – Joshua Grochow Apr 21 '17 at 21:55
  • $\begingroup$ @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? $\endgroup$ – StefanH Apr 24 '17 at 14:18
  • 1
    $\begingroup$ @StefanH: Indeed, you can do that. For many desired statements (such as subadditivity, etc.) you can cook up special versions of UTMs for which the statement holds even though it doesn't hold for general UTMs. I think people prefer to use either plain (C) or prefix-free (K) Kolmogorov complexity because these are fairly natural and minimal assumptions, they were not cooked up in order to satisfy a particular theorem, they are invariant under many natural transformations, and they yield beautiful and useful theories. $\endgroup$ – Joshua Grochow Apr 24 '17 at 15:03

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.