2005/11/21 by David Doty, Doty, David
Computer Science · Mathematics · #Algorithms and Data Compression #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.1 #FOS: Computer and information sciences #H.1.1 #Information Theory (cs.IT) #cs.CC #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0511074
revised conclusion to remove possibly incorrect statements about reversibility of decompression; restated as open question
openalex publication_date 2005/11/21 · arxiv created 2006/08/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Kucera and Gacs independently showed that every infinite sequence is Turing reducible to a Martin-Lof random sequence. This result is extended by showing that every infinite sequence S is Turing reducible to a Martin-Lof random sequence R such that the asymptotic number of bits of R needed to compute n bits of S, divided by n, is precisely the constructive dimension of S. It is shown that this is the optimal ratio of query bits to computed bits achievable with Turing reductions. As an application of this result, a new characterization of constructive dimension is given in terms of Turing reduction compression ratios.