On the construction of effectively random sets
In the 1980s, P. Gács and A. Kučera proved an unexpected result that every binary sequence \(\alpha\) can be reduced to a Martin-Löf random one, i.e., that for every \(\alpha\), there exists a random sequence \(\omega\) from which \(\alpha\) can be effectively reconstructed. The original proof of this result was rather complex. The authors provide a new proof of this result, a proof based on Schnorr's theorem that a sequence is Martin-Löf random if and only if no lower semi-computable (= subcomputable) martingal succeeds on it. This theorem enables the authors to construct \(\omega\) by diagonalizing against the corresponding martingales. The authors show that similar diagonalization can lead to new results: e.g., they show that there exists a random number that is computably enumerable (c.e.) self-reducible -- i.e., for which the computation of \(\omega_n\) can be efficiently reduced to the computation of the values \(\omega_i\) for \(i<n\). This result nicely complements the known result that no random number is Turing-autoreducible (hence no random number is Turing self-reducible), where autoreducible means that we reduce computation of \(\omega_n\) to computation of \(\omega_i\) with \(i\neq n\). Similar diagonalization techniques also apply for a wider class of rec-random sequences, i.e., sequences on which no computable martingale succeeds. In particular, the authors show that there exists a rec-random sequence which is weak truth-table autoreducible. This is probably the best possible result, because it is known that no rec-random sequence is truth-table autoreducible.
- Dimension extractors and optimal decompression
- Optimal redundancy in computations from random oracles
- Dimension 1 sequences are close to randoms
- Two random constructions inside lacunary sets
- Gacs-Kucera theorem
- Things that can be made into themselves
- The Kučera-Gács theorem revisited by Levin
- Relativized depth
- Some Questions in Computable Mathematics
- On the effective generation of set elements within specified ranges
- Calibrating Randomness
- Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
- scientific article; zbMATH DE number 1543075 (Why is no real title available?)
- On the construction of effective random sets
- Selection by recursively enumerable sets
- Solovay functions and their applications in algorithmic randomness
- scientific article; zbMATH DE number 7311154 (Why is no real title available?)
- Working with strong reducibilities above totally -c.e. and array computable degrees
- Logical Approaches to Computational Barriers
- Extending CL-reducibility on array noncomputable degrees
This page was built for publication: On the construction of effectively random sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311758)