0

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

Cupitor
  • 1,281

1 Answers1

1

For every theory, there exists some number $k$, such that for no sequence $S$ it can be proven, that the complexity of $S$ at least $k$.So, the problems you mention must also be uncomputable.

Peter
  • 84,454
  • I don't understand why your argument disproves the claim above. You don't need to explicitly know the complexity of $x$ and check whether $y$ has a larger complexity or not? – Cupitor Aug 19 '15 at 17:33