Limit Complexities, Minimal Descriptions, and $n$-Randomness

Rodney Downey, Lu Liu, Keng Meng Ng +1

Let $K$ denote prefix-free Kolmogorov Complexity, and $K^A$ denote it relative to an oracle $A$. We show that for any $n$, $K^{{\varnothing }^{(n)}}$ is definable purely in terms of the…