1
$\begingroup$

It is a known result that Kolmogorov complexity is not computable for every arbitrary sequence. I wonder whether the following problem is computable or not:

"Given $x$ and $y$ as two sequences, whether $K(x)\overset{+}{=}K(y)$, where $\overset{+}{=}$ means equality in Kolmogorov complexity sense."

My next question is a generalisation of this one, i.e. whether the following is computable:

"Given $x$ and $y$ as two sequences, whether $K(x)\overset{+}{<}K(y)$, where $\overset{+}{<}$ means strictly smaller in Kolmogorov complexity sense."

$\endgroup$
  • 3
    $\begingroup$ What is "equality in the Komolgorov complexity sense"? $\endgroup$ – cody Aug 19 '15 at 17:03
5
$\begingroup$

I think of the following argument: if we can check whether two sequences have equal Kolmogorov complexity we can write a program that enumerates all sequences of length $\le N$ and divides them into equivalence classes.

We know that $K(x) \le |x|$. So, we have at most $N$ equivalence classes of sequences. One of this classes should be of size at least $2^{N+1}/N$. All the sequences in this class have Kolmogorov complexity at least $(N+1 - \log N) \ge N / 2$ (as we have at most $2^{n}$ sequences of Kolmogorov complexity $n$).

So, now we have a program that can generate a sequence of Kolmogorov complexity at least $N/2$ for any given $N$. But this program itself has some fixed length $L$. Choosing $N$ to be greater than $2(L + \log N)$ leads to contradiction.

The same argument should work for $\overset{+}{<}$.

(I omited an additive constant that depends on the description language we choose to define $K(x)$.)

$\endgroup$

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.