Cone avoidance and randomness preservation

DOI10.1016/j.apal.2015.03.001zbMath1371.03052OpenAlexW2001471861MaRDI 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 complexityalgorithmic randomnesspartial randomnessPA-completenessbasis theoremsK-triviality

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) First-order arithmetic and fragments (03F30) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)

Related Items (6)

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

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

This page was built for publication: Cone avoidance and randomness preservation