On the construction of effectively random sets

DOI10.2178/jsl/1096901772zbMath1090.03011OpenAlexW2170481824MaRDI QIDQ5311758

Wolfgang Merkle, Nenad Mihailovic

Publication date: 29 August 2005

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1096901772

zbMATH Keywords

diagonalizationMartin-Löf randomnesscomputable martingalerec-random sequence

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Recursively (computably) enumerable sets and degrees (03D25)

Related Items

Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers, Optimal redundancy in computations from random oracles, Dimension 1 sequences are close to randoms, The Kučera-Gács theorem revisited by Levin, Relativized depth, Some Questions in Computable Mathematics, Solovay functions and their applications in algorithmic randomness, Things that can be made into themselves, Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees, Dimension extractors and optimal decompression, Calibrating Randomness

Cites Work

• Unnamed Item
• Almost everywhere high nonuniform complexity
• Every sequence is reducible to a random one
• On the Autoreducibility of Random Sequences
• A unified approach to the definition of random sequences
• The definition of random sequences