Limit on the computational power of $\mathrm{C}$-random strings

Alexey Milovanov

We construct a universal decompressor $U$ for plain Kolmogorov complexity ${\mathrm{C}}_U$ such that the Halting Problem cannot be decided by any polynomial-time oracle machine with…