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?

Improve this question
$\endgroup$
4
  • 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
    Commented Sep 3, 2017 at 1:36
  • 1
    $\begingroup$ Also, is the conditional Kolmogorov complexity computable? $\endgroup$
    – Evil
    Commented Sep 3, 2017 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
    Commented Sep 3, 2017 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
    Commented Sep 3, 2017 at 3:45

1 Answer 1

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Sep 3, 2017 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
    Commented Sep 3, 2017 at 14:25

Your Answer

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

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