"Checking equality for Kolmogorov complexity of two sequences" is computable?

Question

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."

Answer 1

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)$.)