On relative randomness

DOI10.1016/0168-0072(93)90209-VzbMath0788.68068MaRDI QIDQ688792

Antonín Kučera

Publication date: 2 June 1994

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

random setalgorithmic complexity theoryconstructive measure 0relative randomness

Mathematics Subject Classification ID

Constructive and recursive analysis (03F60) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Automata and formal grammars in connection with logical questions (03D05) Other constructive mathematics (03F65)

Related Items

Turing incomparability in Scott sets, COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS, STRONG JUMP-TRACEABILITY, A measure-theoretic proof of Turing incomparability, Truth-table Schnorr randomness and truth-table reducible randomness, Randomness, relativization and Turing degrees, HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT, Trivial Reals, Lowness for the class of random sets, Mass Problems and Randomness, Randomness and Computability: Open Questions, Calibrating Randomness, Lowness properties and randomness, Unified characterizations of lowness properties via Kolmogorov complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classical recursion theory. The theory of functions and sets of natural numbers
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• Von Mises' definition of random sequences reconsidered
• Algorithms and Randomness
• The axiomatization of randomness
• The definition of random sequences
• ∏ 0 1 Classes and Degrees of Theories