On relative randomness

DOI10.1016/0168-0072(93)90209-VMaRDI QIDQ688792zbMATH OpenFDO

Authors 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

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)

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

Cites work

• scientific article; zbMATH DE number 4156423 (Why is no real title available?)
• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1142293 (Why is no real title available?)
• scientific article; zbMATH DE number 3995657 (Why is no real title available?)
• scientific article; zbMATH DE number 4118353 (Why is no real title available?)
• Algorithms and Randomness
• Classical recursion theory. The theory of functions and sets of natural numbers
• Information, randomness and incompleteness. Papers on algorithmic information theory
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• The axiomatization of randomness
• The definition of random sequences
• Von Mises' definition of random sequences reconsidered
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(33)

• scientific article; zbMATH DE number 4054673 (Why is no real title available?)
• scientific article; zbMATH DE number 4119313 (Why is no real title available?)
• Algorithmically random universal algebras
• Strong jump-traceability
• Trivial Reals
• Computuing \(K\)-trivial sets by incomplete random sets
• scientific article; zbMATH DE number 1531917 (Why is no real title available?)
• scientific article; zbMATH DE number 4176096 (Why is no real title available?)
• Randomness relative to Cantor expansions
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• Truth-table Schnorr randomness and truth-table reducible randomness
• On Empirical Meaning of Randomness with Respect to a Real Parameter
• On elementary computability-theoretic properties of algorithmic randomness
• Algorithmic randomness and monotone complexity on product space
• Randomness in post-selected events
• Lowness properties and randomness
• Random non-cupping revisited
• Propagation of partial randomness
• scientific article; zbMATH DE number 758020 (Why is no real title available?)
• Mass Problems and Randomness
• Optimal redundancy in computations from random oracles
• Unified characterizations of lowness properties via Kolmogorov complexity
• Comparing notions of randomness
• Calibrating Randomness
• Randomness and Computability: Open Questions
• Lowness for the class of random sets
• scientific article; zbMATH DE number 4041257 (Why is no real title available?)
• Separations of non-monotonic randomness notions
• Randomness, relativization and Turing degrees
• Relative randomness and cardinality
• Randomness for non-computable measures
• Turing incomparability in Scott sets
• A measure-theoretic proof of Turing incomparability

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)