On relative randomness

DOI10.1016/0168-0072(93)90209-VzbMATH Open0788.68068MaRDI QIDQ688792FDOQ688792

Authors: Antonín Kučera 

Publication date: 2 June 1994

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

Recommendations

• scientific article; zbMATH DE number 1531917
• scientific article; zbMATH DE number 4054673
• The Kolmogorov complexity of random reals
• Lowness for the class of random sets
• Algorithmic randomness and measures of complexity

zbMATH Keywords

random setalgorithmic complexity theoryconstructive measure 0relative randomness

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The definition of random sequences
• ∏ 0 1 Classes and Degrees of Theories
• Von Mises' definition of random sequences reconsidered
• Title not available (Why is that?)
• Classical recursion theory. The theory of functions and sets of natural numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Information, randomness and incompleteness. Papers on algorithmic information theory
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• Title not available (Why is that?)
• The axiomatization of randomness
• Title not available (Why is that?)
• Algorithms and Randomness

Cited In (30)

• Relative randomness and cardinality
• Title not available (Why is that?)
• Randomness for non-computable measures
• Title not available (Why is that?)
• Comparing notions of randomness
• STRONG JUMP-TRACEABILITY
• Randomness, relativization and Turing degrees
• Random non-cupping revisited
• Randomness relative to Cantor expansions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Calibrating Randomness
• Randomness and Computability: Open Questions
• Mass Problems and Randomness
• Title not available (Why is that?)
• Turing incomparability in Scott sets
• Separations of non-monotonic randomness notions
• Unified characterizations of lowness properties via Kolmogorov complexity
• A measure-theoretic proof of Turing incomparability
• On Empirical Meaning of Randomness with Respect to a Real Parameter
• Lowness properties and randomness
• Trivial Reals
• Lowness for the class of random sets
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• Truth-table Schnorr randomness and truth-table reducible randomness
• Title not available (Why is that?)
• Randomness in post-selected events
• On elementary computability-theoretic properties of algorithmic randomness
• Algorithmic randomness and monotone complexity on product space
• Computuing \(K\)-trivial sets by incomplete random sets

This page was built for publication: On relative randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688792)