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)

Full work available at URL https://doi.org/10.1016/0168-0072(93)90209-V

zbMATH Keywords

algorithmic complexity theoryconstructive measure 0random setrelative randomness

Mathematics Subject Classification ID

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

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

• ∏ 0 1 Classes and Degrees of Theories
• Algorithms and Randomness
• Classical recursion theory. The theory of functions and sets of natural numbers
• 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?)
• 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

Cited in

(34)

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

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)