Cone avoidance and randomness preservation

DOI10.1016/j.apal.2015.03.001zbMath1371.03052MaRDI QIDQ2344623

Stephen G. Simpson, Frank Stephan

Publication date: 15 May 2015

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

Full work available at URL: https://doi.org/10.1016/j.apal.2015.03.001

zbMATH Keywords

Kolmogorov complexity; algorithmic randomness; partial randomness; PA-completeness; basis theorems; K-triviality

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03F30: First-order arithmetic and fragments

03D28: Other Turing degree structures

03D32: Algorithmic randomness and dimension

Related Items

A computable analysis of majorizing martingales, DEGREES OF RANDOMIZED COMPUTABILITY, When does randomness come from randomness?, Schnorr randomness for noncomputable measures, Two more characterizations of \(K\)-triviality, Highness properties close to PA completeness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Propagation of partial randomness
• A nonstandard counterpart of WWKL
• Mass problems associated with effectively closed sets
• Effectively closed sets of measures and randomness
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Information-theoretic characterizations of recursive infinite strings
• Computable structures and the hyperarithmetical hierarchy
• Independence, relative randomness, and PA degrees
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Uniform test of algorithmic randomness over a general space
• Lowness properties and randomness
• On partial randomness
• Randomness for non-computable measures
• Chaitin's halting probability and the compression of strings using oracles
• Kolmogorov complexity and the Recursion Theorem
• Algorithmic Randomness and Complexity
• Mass Problems and Randomness
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Randomness and differentiability
• On initial segment complexity and degrees of randomness
• Degrees joining to 0′
• Relations between varieties of kolmogorov complexities
• Measures and their random reals
• Almost everywhere domination and superhighness
• Degrees of unsolvability of continuous functions
• ∏ 0 1 Classes and Degrees of Theories