Randomness, relativization and Turing degrees

DOI10.2178/jsl/1120224726zbMath1090.03013OpenAlexW2058444173MaRDI 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

zbMATH Keywords

Kolmogorov complexity randomness Schnorr randomness Turing degree of a real

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Other Turing degree structures (03D28)

Related Items (58)

Demuth’s Path to Randomness ⋮ Reducibilities relating to Schnorr randomness ⋮ Relating and contrasting plain and prefix Kolmogorov complexity ⋮ On the uniform computational content of the Baire category theorem ⋮ Randomness, Computation and Mathematics ⋮ Initial segment complexities of randomness notions ⋮ Low for random reals and positive-measure domination ⋮ DEGREES OF RANDOMIZED COMPUTABILITY ⋮ Randomness and universal machines ⋮ LUZIN’S (N) AND RANDOMNESS REFLECTION ⋮ Genericity and UD-random reals ⋮ THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY ⋮ Depth, Highness and DNR Degrees ⋮ DEEP CLASSES ⋮ Continuous randomness via transformations of 2-random sequences ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ On initial segment complexity and degrees of randomness ⋮ Effectively approximating measurable sets by open sets ⋮ Growth and irreducibility in path-incompressible trees ⋮ Strength and Weakness in Computable Structure Theory ⋮ Effective Bi-immunity and Randomness ⋮ Demuth randomness and computational complexity ⋮ Limit complexities revisited ⋮ Schnorr trivial reals: a construction ⋮ Convergence of random series and the rate of convergence of the strong law of large numbers in game-theoretic probability ⋮ ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY ⋮ The Information Content of Typical Reals ⋮ Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs ⋮ Lowness of higher randomness notions ⋮ Canonical immunity and genericity ⋮ Schnorr trivial sets and truth-table reducibility ⋮ Strong reductions in effective randomness ⋮ Schnorr Trivial Reals: A construction ⋮ Effective Randomness for Computable Probability Measures ⋮ On low for speed oracles ⋮ Relativized Schnorr tests with universal behavior ⋮ Coherence of reducibilities with randomness notions ⋮ DEMUTH’S PATH TO RANDOMNESS ⋮ Hyperimmune-free degrees and Schnorr triviality ⋮ RELATIVIZING CHAITIN'S HALTING PROBABILITY ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Difference randomness ⋮ Lowness for Kurtz randomness ⋮ Highness properties close to PA completeness ⋮ BEING LOW ALONG A SEQUENCE AND ELSEWHERE ⋮ On a conjecture of Dobrinen and Simpson concerning almost everywhere domination ⋮ Randomness and initial segment complexity for measures ⋮ Constructive equivalence relations on computable probability measures ⋮ Randomness and Computability: Open Questions ⋮ Calibrating Randomness ⋮ When van Lambalgen’s Theorem fails ⋮ Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness ⋮ Unified characterizations of lowness properties via Kolmogorov complexity ⋮ On partial randomness ⋮ Integer valued betting strategies and Turing degrees ⋮ Trivial measures are not so trivial ⋮ KL-randomness and effective dimension under strong reducibility

Cites Work

This page was built for publication: Randomness, relativization and Turing degrees