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 set; algorithmic complexity theory; constructive measure 0; relative randomness

Mathematics Subject Classification ID

03F60: Constructive and recursive analysis

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D05: Automata and formal grammars in connection with logical questions

03F65: Other constructive mathematics

Related Items

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

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