Every Sequence is Decompressible from a Random One

Details Every Sequence is Decompressible from a Random One Every Sequence is Decompressible from a Random One

2005-11-21

arxiv.org/abs/cs/0511074v5

Computer Science

Information Theory

revised conclusion to remove possibly incorrect statements about reversibility of decompression; restated as open question

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Every Sequence is Decompressible from a Random One does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Every Sequence is Decompressible from a Random One, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Every Sequence is Decompressible from a Random One will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-291013