<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-04-20T11:59:47.257Z
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.
StefanH
CC BY-SA 3.0
2017-04-21T00:26:32.863Z
So if your encoding is not self-delimiting, how do you know where the program for $f$ ends and the program for $g$ begins?
Sasho Nikolov
CC BY-SA 3.0
2017-04-21T21:55:12.323Z
@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](https://en.wikipedia.org/wiki/Admissible_numbering), you can't "encode the parameters in the machines itself with just a constant overhead."
Joshua Grochow
CC BY-SA 3.0
2017-04-24T14:18:31.343Z
@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?
StefanH
CC BY-SA 3.0
2017-04-24T15:03:50.067Z
@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.
Joshua Grochow
CC BY-SA 3.0
2017-04-25T08:28:44.900Z
"General UTM" - in some way we fix something if we prescribe how general UTMs inputs look like, i.e. a programm coding and its input coded as a tuple, other ways might be conceivable too so this is not the most "general". But anyway thank, clarified a lot!
StefanH
CC BY-SA 3.0
2017-04-20T11:26:35.473Z
2017-04-21T10:50:14.700Z
2017-04-21T10:50:14.700Z
Yuval Filmus
<p>Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example <a href="https://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="noreferrer">on wikipedia</a>. </p>

<p>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).</p>

<p>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</p>

<blockquote>
  <p>h() { <br/>
   return concat(f(a1, ..., ak), g(b1,...,bl)); <br/>
  }</p>
</blockquote>

<p>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).</p>

<p>Hence $K'(xy) \le K'(x) + K'(y) + C$.</p>

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

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

CC BY-SA 3.0
2017-04-20T11:14:59.263Z
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?
Aryeh
CC BY-SA 3.0
2017-04-20T11:22:01.170Z
@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...
StefanH
CC BY-SA 3.0
2017-04-20T11:29:42.453Z
@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.
Yuval Filmus
CC BY-SA 3.0
2017-04-20T11:36:43.993Z
Oh I see -- the issue is that the number of states is const * description length of the TM, while we need const + ?
Aryeh
CC BY-SA 3.0
2017-04-20T11:42:59.923Z
@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)}$.
Yuval Filmus
CC BY-SA 3.0
2017-04-20T11:47:05.480Z
I think that's equivalent to what I said -- # of states and description length are not equivalent up to an additive constant (though YES up to a multiplicative constant).
Aryeh
CC BY-SA 3.0
2017-04-20T12:03:03.597Z
The description length is $\Theta(n\log n)$, which is not linear in $n$.
Yuval Filmus
CC BY-SA 3.0
2017-04-20T12:11:28.207Z
Dope, of course! From each state, you need to specify the indices of the other states to which it can transition, hence the extra log(n). Thanks!
Aryeh
<fl.formal-languages><computability><randomness><kolmogorov-complexity><descriptive-complexity>
Where does the "intuitive" understanding of Kolmogorov complexity fails
StefanH
# Where does the "intuitive" understanding of Kolmogorov complexity fails

(Asked by: username_0 on 2017-04-20)

Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example [on wikipedia](https://en.wikipedia.org/wiki/Kolmogorov_complexity).

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.

**Tags:** fl.formal-languages, computability, randomness, kolmogorov-complexity, descriptive-complexity

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1 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...  
> **username_2**: @username_1 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.  
> **username_1**: Oh I see -- the issue is that the number of states is const * description length of the TM, while we need const + ?  
> **username_2**: @username_1 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)}$.  
> **username_1**: I think that's equivalent to what I said -- # of states and description length are not equivalent up to an additive constant (though YES up to a multiplicative constant).  
> **username_2**: The description length is $\Theta(n\log n)$, which is not linear in $n$.  
> **username_1**: Dope, of course! From each state, you need to specify the indices of the other states to which it can transition, hence the extra log(n). Thanks!  

---

## 1 answers

### Answer by username_2 on 2017-04-20. Score: 7 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: So if your encoding is not self-delimiting, how do you know where the program for $f$ ends and the program for $g$ begins?  
> **username_4**: @username_0: 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](https://en.wikipedia.org/wiki/Admissible_numbering), you can't "encode the parameters in the machines itself with just a constant overhead."  
> **username_0**: @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?  
> **username_4**: @username_0: 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.  
> **username_0**: "General UTM" - in some way we fix something if we prescribe how general UTMs inputs look like, i.e. a programm coding and its input coded as a tuple, other ways might be conceivable too so this is not the most "general". But anyway thank, clarified a lot!  

---

