Anti-Complex Sets and Reducibilities with Tiny Use

DOI10.2178/jsl.7804170zbMath1307.03025arXiv1110.0304OpenAlexW1988580980MaRDI QIDQ5407055

Noam Greenberg, Johanna N. Y. Franklin, Frank Stephan, Guohua Wu

Publication date: 4 April 2014

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.0304

zbMATH Keywords

Kolmogorov complexitySchnorr trivial setsprefix-free machinesr.e. traceable degreesreducibility with tiny useweak truth-table degrees

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32)

Related Items (7)

STRONG JUMP-TRACEABILITY ⋮ On effectively closed sets of effective strong measure zero ⋮ A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES ⋮ Randomness for computable measures and initial segment complexity ⋮ Kobayashi compressibility ⋮ Reductions between types of numberings ⋮ Unified characterizations of lowness properties via Kolmogorov complexity

This page was built for publication: Anti-Complex Sets and Reducibilities with Tiny Use