1
$\begingroup$

It seems intuitive that conditional Kolmogorov complexity is only zero when the bitstrings are the same, and otherwise is greater than 0. I.e. if $b_1 = b_2$, then $K(b_1|b_2) = 0$, otherwise $K(b_1|b_2) > 0$.

However, if that is the case, then we could break a long bitstring into many smaller, different bitstrings, and then use conditional Kolmogorov complexity to establish a lower bound on the long bitstring's Kolmogorov complexity.

E.g., original bitstring is $\mathcal{B}$. It is broken into different, smaller bitstrings $b_1,b_2,\ldots,b_n$. We then use conditional Kolmogorov complexity to establish a lower bound on $K(\mathcal{B})$, in the following way,

\begin{align*} K(\mathcal{B}) &= K(b_1,b_2,\ldots,b_n) \\ &= K(b_1) + K(b_2|b_1) + \ldots + K(b_n|b_1,b_2,\ldots,b_{n-1}) + O(log(K(b_1,b_2,\ldots,b_n)))\\ &\geq n. \end{align*}

The equality is not strict, there are errors involved, which may invalidate the argument.

As the bitstring length grows, we can continue to grow the lower bound $n$ arbitrarily large, since there are a greater number of distinct smaller bitstrings that can be used to construct the large bitstring. This appears to violate Chaitin's incompleteness theorem, which states with a fixed axiomatic system there is a limit $\mathcal{L}$ above which we cannot prove $K(\mathcal{B}) > \mathcal{L}$.

What am I missing here?

$\endgroup$
  • 1
    $\begingroup$ Afaik Kolmogorov-Chaitin theorem, it was attributed to both. There is an error, it is not subadditive, $C(x, y) = C (x) + C (y) + \mathcal O (\log(\min(C(x), C (y))))$ $\endgroup$ – Evil Sep 3 '17 at 1:36
  • 1
    $\begingroup$ Also, is the conditional Kolmogorov complexity computable? $\endgroup$ – Evil Sep 3 '17 at 1:48
  • 1
    $\begingroup$ No, it is not being computed in my argument. Each of the conditional terms in the summation are more than 0 based on the initial premise, which allows me to lower bound with $n$ (the number of conditionals). Since this results in a contradiction, the conclusion I draw is $K(b_2|b_1) = 0$ in cases where $b_1 \neq b_2$, which is counter intuitive. $\endgroup$ – yters Sep 3 '17 at 2:46
  • $\begingroup$ The additional term is added to all "substrings", not once if I read correctly the fix. It has the flaw, that in the splitting you end up with atomic values, which are incompressible, so the sum of substrings will actually be $n$, or bigger, because of overhead to encode all strings separately, but this is in fact an upper bound, not lower bound, since the original string represented as is would be shorter (or equal) to sum of substrings, which defies the idea. $\endgroup$ – Evil Sep 3 '17 at 3:45
1
$\begingroup$

The answer depends on whether your encoding is prefix-free or not, and in the latter case, on your universal Turing machine.

There are two variants of Kolmogorov complexity: one in which the set of programs form a prefix-free code, and one in which there is no such requirement. For the first variant, the Kolmogorov complexity is always positive. For the second variant, the universal Turing machine can do whatever it wants given an empty program (or indeed, any fixed program). You can arrange that $K(x_1|x_2) = 0$ for your choice of $x_1,x_2$, for example.

$\endgroup$
  • $\begingroup$ For the prefix free variant, if the conditional Kolmogorov complexity is always positive, does that result in the contradiction with Chaitin's incompleteness theorem? $\endgroup$ – yters Sep 3 '17 at 14:24
  • $\begingroup$ No, the theorem only states that there is a limit $L$ above which you cannot $K(x) > L$. Evidently this limit is larger than 0. $\endgroup$ – Yuval Filmus Sep 3 '17 at 14:25

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.