Kučera and Gács independently showed that every infinite sequence is Turing reducible to a Martin-Löf random sequence. This result is extended by showing that every infinite sequence S is Turing reducible to a Martin-Löf 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.
Doty REF revisited the Kučera-Gács theorem from the viewpoint of constructive dimension.
Every Sequence is Decompressible from a Random One
ArXiv
ArXiv
Mathematics Computer Science