Randomness, relativization and Turing degrees
From MaRDI portal
Publication:5718673
DOI10.2178/jsl/1120224726zbMath1090.03013MaRDI QIDQ5718673
André Nies, Sebastiaan A. Terwijn, Frank Stephan
Publication date: 16 January 2006
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.4984
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
03D80: Applications of computability and recursion theory
03D28: Other Turing degree structures
Related Items
THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY, ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY, The Information Content of Typical Reals, Schnorr Trivial Reals: A construction, Effective Randomness for Computable Probability Measures, DEGREES OF RANDOMIZED COMPUTABILITY, LUZIN’S (N) AND RANDOMNESS REFLECTION, RANDOMNESS NOTIONS AND REVERSE MATHEMATICS, Canonical immunity and genericity, BEING LOW ALONG A SEQUENCE AND ELSEWHERE, Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness, Low for random reals and positive-measure domination, DEEP CLASSES, On a conjecture of Dobrinen and Simpson concerning almost everywhere domination, Continuous randomness via transformations of 2-random sequences, On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1, Growth and irreducibility in path-incompressible trees, Reducibilities relating to Schnorr randomness, Relating and contrasting plain and prefix Kolmogorov complexity, Effectively approximating measurable sets by open sets, Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs, Demuth randomness and computational complexity, Convergence of random series and the rate of convergence of the strong law of large numbers in game-theoretic probability, Randomness and universal machines, Schnorr trivial reals: a construction, Lowness of higher randomness notions, Relativized Schnorr tests with universal behavior, Constructive equivalence relations on computable probability measures, On the uniform computational content of the Baire category theorem, Strong reductions in effective randomness, Coherence of reducibilities with randomness notions, Limit complexities revisited, On low for speed oracles, Highness properties close to PA completeness, Randomness and initial segment complexity for measures, KL-randomness and effective dimension under strong reducibility, Unified characterizations of lowness properties via Kolmogorov complexity, Integer valued betting strategies and Turing degrees, Trivial measures are not so trivial, On partial randomness, Initial segment complexities of randomness notions, DEMUTH’S PATH TO RANDOMNESS, Demuth’s Path to Randomness, Randomness, Computation and Mathematics, Genericity and UD-random reals, Depth, Highness and DNR Degrees, Strength and Weakness in Computable Structure Theory, Effective Bi-immunity and Randomness, Difference randomness, RELATIVIZING CHAITIN'S HALTING PROBABILITY, Hierarchy of Computably Enumerable Degrees II, Randomness and Computability: Open Questions, Calibrating Randomness, When van Lambalgen’s Theorem fails, On initial segment complexity and degrees of randomness, Schnorr trivial sets and truth-table reducibility, Hyperimmune-free degrees and Schnorr triviality, Lowness for Kurtz randomness
Cites Work
- Unnamed Item
- On relative randomness
- Computational randomness and lowness
- Randomness and Recursive Enumerability
- Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
- A Theory of Program Size Formally Identical to Information Theory
- Lowness for the class of random sets
- Complexity oscillations in infinite binary sequences
- A unified approach to the definition of random sequences
- The definition of random sequences
