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

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

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

<p>The same argument should work for $\overset{+}{&lt;}$.</p>

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

CC BY-SA 3.0
2015-08-19T16:16:58.410Z
2015-08-20T10:37:32.317Z
2015-08-20T10:37:32.317Z
avsmal
<p>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:</p>

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

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

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

CC BY-SA 3.0
2015-08-19T17:03:26.490Z
What is "equality in the Komolgorov complexity sense"?
cody
<kolmogorov-complexity><complexity>
"Checking equality for Kolmogorov complexity of two sequences" is computable?
Naji
# "Checking equality for Kolmogorov complexity of two sequences" is computable?

(Asked by: username_0 on 2015-08-19)

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

**Tags:** kolmogorov-complexity, complexity
> **Comments:**
> **username_1**: What is "equality in the Komolgorov complexity sense"?  

---

## 1 answers

### Answer by username_2 on 2015-08-19. Score: 5

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


---

