2022/08/05 by Rodney G. Downey, Downey, Rodney, Lu Liu +5
Computer Science · Mathematics · #Advanced Topology and Set Theory #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO)
paper · pdf · doi:10.48550/arxiv.2208.02982
openalex publication_date 2022/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let K denote prefix-free Kolmogorov Complexity, and KA denote it relative to an oracle A. We show that for any n, K^∅(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 Δ20 sets of mimimal descriptions.