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.

Improve this question
$\endgroup$
8
  • $\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 11:42

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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