0
$\begingroup$

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)

$\endgroup$
13
  • $\begingroup$ The link gives a proof that the halting problem is solvable using a Kolmogorov complexity oracle. What is missing? $\endgroup$ Apr 4 at 21:59
  • $\begingroup$ @YuvalFilmus No, the link only prove Kolmogorov unsolvable $\endgroup$
    – l4m2
    Apr 5 at 5:30
  • $\begingroup$ 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. $\endgroup$ Apr 5 at 6:06
  • $\begingroup$ @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 $\endgroup$
    – l4m2
    Apr 5 at 8:05
  • $\begingroup$ 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. $\endgroup$ Apr 5 at 10:39

This site is temporarily in read only mode and not accepting new answers.

Browse other questions tagged .