Computer Science – Computational Complexity
Scientific paper
2006-06-19
Computer Science
Computational Complexity
This report was combined with a different conference paper "Every Sequence is Decompressible from a Random One" (cs.IT/0511074
Scientific paper
A *dimension extractor* is an algorithm designed to increase the effective dimension -- i.e., the amount of computational randomness -- of an infinite binary sequence, in order to turn a "partially random" sequence into a "more random" sequence. Extractors are exhibited for various effective dimensions, including constructive, computable, space-bounded, time-bounded, and finite-state dimension. Using similar techniques, the Kucera-Gacs theorem is examined from the perspective of decompression, by showing that every infinite sequence S is Turing reducible to a Martin-Loef 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, which is shown to be the optimal ratio of query bits to computed bits achievable with Turing reductions. The extractors and decompressors that are developed lead directly to new characterizations of some effective dimensions in terms of optimal decompression by Turing reductions.
No associations
LandOfFree
Dimension Extractors and Optimal Decompression 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 Dimension Extractors and Optimal Decompression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dimension Extractors and Optimal Decompression will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-304528