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