On the construction of effectively random sets

DOI10.2178/JSL/1096901772MaRDI QIDQ5311758zbMATH OpenOpenAlexFDO

Authors 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

computable martingalediagonalizationMartin-Löf randomnessrec-random sequence

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1929969
• Some results on effective randomness
• scientific article; zbMATH DE number 1929940
• Computably enumerable sets below random sets
• Automata, Languages and Programming

Cites work

• A unified approach to the definition of random sequences
• Almost everywhere high nonuniform complexity
• Every sequence is reducible to a random one
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• On the Autoreducibility of Random Sequences
• The definition of random sequences

Cited in

(20)

• 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?)
• scientific article; zbMATH DE number 1929969 (Why is no real title available?)
• 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)