Unified characterizations of lowness properties via Kolmogorov complexity
From MaRDI portal
Publication:2339957
DOI10.1007/s00153-014-0413-8zbMath1338.03083OpenAlexW2161536405MaRDI QIDQ2339957
Takayuki Kihara, Kenshi Miyabe
Publication date: 14 April 2015
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00153-014-0413-8
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)
Related Items (3)
Reducibilities relating to Schnorr randomness ⋮ On effectively closed sets of effective strong measure zero ⋮ ON A METRIC GENERALIZATION OF THE tt-DEGREES AND EFFECTIVE DIMENSION THEORY
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Van Lambalgen's theorem and high degrees
- On relative randomness
- Randomness and lowness notions via open covers
- Schnorr trivial reals: a construction
- Superhighness
- Classical recursion theory. Vol. II
- A characterization of strong measure zero sets
- Schnorr triviality and its equivalent notions
- On effectively closed sets of effective strong measure zero
- Hyperimmunity in \(2^{\mathbb N}\)
- Small \(\Pi^{0}_{1}\) classes
- Lowness properties and randomness
- Kolmogorov-Loveland randomness and stochasticity
- Computational randomness and lowness
- Lowness notions, measure and domination
- Uniform Kurtz randomness
- Truth-table Schnorr randomness and truth-table reducible randomness
- Jump inversions inside effectively closed sets and applications to randomness
- Kolmogorov complexity and the Recursion Theorem
- On Schnorr and computable randomness, martingales, and machines
- Algorithmic Randomness and Complexity
- Traceable Sets
- Lowness and nullsets
- When van Lambalgen’s Theorem fails
- Schnorr trivial sets and truth-table reducibility
- Members of Random Closed Sets
- Finding paths through narrow and wide trees
- Hyperimmune-free degrees and Schnorr triviality
- Lowness for Kurtz randomness
- Von Mises' definition of random sequences reconsidered
- Algorithmic Information Theory
- Lowness for the class of random sets
- Schnorr triviality and genericity
- Using random sets as oracles
- Schnorr randomness
- Anti-Complex Sets and Reducibilities with Tiny Use
- Lowness for the Class of Schnorr Random Reals
- Π10 classes with complex elements
- New Computational Paradigms
- Randomness, relativization and Turing degrees
- Van Lambalgen's theorem for uniformly relative Schnorr and computable randomness
- Theory and Applications of Models of Computation
This page was built for publication: Unified characterizations of lowness properties via Kolmogorov complexity
