# Can a Kolmogorov complexity oracle solve halting problem?

I can find https://www.nearly42.org/cstheory/halting_to_kolmogorov/ but the halting problem part is unrelated to proof that kolmogorov can't be solved(still that assume it solvable and output a longer uncompressable string)

• The link gives a proof that the halting problem is solvable using a Kolmogorov complexity oracle. What is missing? Apr 4 at 21:59
• @YuvalFilmus No, the link only prove Kolmogorov unsolvable
– l4m2
Apr 5 at 5:30
• Are you sure? It seems to reduce the halting problem to Kolmogorov complexity, and so deduce computability of the former from that of the latter. Apr 5 at 6:06
• @YuvalFilmus In the proof Kolmogorov appears first at Now suppose that Kolmogorov complexity $C(x)$ of a string $x$ is computable where BB no longer appear
– l4m2
Apr 5 at 8:05
• Under the assumption that Kolmogorov complexity can be computed, it is shown how to solve the halting problem. So I'm still not sure what is missing. Apr 5 at 10:39