Limit Complexities, Minimal Descriptions, and n-Randomness

arXiv2208.02982MaRDI QIDQ6407048FDOQ6407048

Authors: Rodney G. Downey, Lu Liu, Keng Meng Ng, Daniel Turetsky 

Publication date: 5 August 2022

Abstract: Let $K$ denote prefix-free Kolmogorov Complexity, and $K^A$ denote it relative to an oracle $A$. We show that for any $n$, $K^{emptyse{t}^{(n)}}$ is definable purely in terms of the unrelativized notion $K$. It was already known that 2-randomness is definable in terms of $K$ (and plain complexity $C$) as those reals which infinitely often have maximal complexity. We can use our characterization to show that $n$-randomness is definable purely in terms of $K$. To do this we extend a certain ``limsup formula from the literature, and apply Symmetry of Information. This extension entails a novel use of semilow sets, and a more precise analysis of the complexity of $Delt{a}_2^0$ sets of mimimal descriptions.

This page was built for publication: Limit Complexities, Minimal Descriptions, and $n$-Randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6407048)