Characterizing the strongly jump-traceable sets via randomness
type: Item
instance of: scholarly article
title: Characterizing the strongly jump-traceable sets via randomness
zbMATH Open document ID: 1257.03068
author: Noam Greenberg
author: Denis R. Hirschfeldt
author: André Nies
published in: Advances in Mathematics
publication date: 2012-10-16T00:00:00Z
full work available at URL: https://arxiv.org/abs/1109.6749
reviewed by: Liang Yu
Mathematics Subject Classification ID: 03D32
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D80
Mathematics Subject Classification ID: 03F60
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 6094112
zbMATH Keywords: strongly jump-traceable sets
zbMATH Keywords: randomness
zbMATH Keywords: superlowness
MaRDI profile type: Publication
OpenAlex ID: W1970189970
arXiv ID: 1109.6749
cites work: 𝐾-trivial degrees and the jump-traceability hierarchy
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Strong jump-traceability. I: The computably enumerable case
cites work: MASS PROBLEMS AND HYPERARITHMETICITY
cites work: Q3669408
cites work: Inherent enumerability of strong jump-traceability
cites work: Strong jump-traceability. II: \(K\)-triviality
cites work: Algorithmic Randomness and Complexity
cites work: Q4460833
cites work: Calibrating Randomness
cites work: Q5619076
cites work: Lowness properties and approximations of the jump
cites work: Every sequence is reducible to a random one
cites work: A random set which only computes strongly jump-traceable c.e. sets
cites work: Benign cost functions and lowness properties
cites work: Strong jump-traceability and Demuth randomness
cites work: Using random sets as oracles
cites work: Q3469096
cites work: ∏ 0 1 Classes and Degrees of Theories
cites work: Kolmogorov complexity and the Recursion Theorem
cites work: Superhighness
cites work: Demuth randomness and computational complexity
cites work: Q3758821
cites work: Q4723720
cites work: Lowness for the class of random sets
cites work: Randomness and Computability: Open Questions
cites work: A Refinement of Lown and Highn for the R.E. Degrees
cites work: On strongly jump traceable reals
cites work: Lowness properties and randomness
cites work: Q5494235
cites work: Superhighness and Strong Jump Traceability
cites work: Q3611832
cites work: Computability and Randomness
cites work: Q3096589
cites work: Computably enumerable sets below random sets
cites work: Almost everywhere domination and superhighness
cites work: Q4863250
cites work: Q3567853
cites work: The axiomatization of randomness
DOI: 10.1016/J.AIM.2012.06.005
Recommended article: A random set which only computes strongly jump-traceable c.e. sets
Recommended article: Strong jump-traceability and Demuth randomness
Recommended article: Inherent enumerability of strong jump-traceability
Recommended article: Strong jump-traceability. II: \(K\)-triviality
Recommended article: Strong jump-traceability. I: The computably enumerable case
Recommended article: On strongly jump traceable reals
Recommended article: Jump inversions inside effectively closed sets and applications to randomness
Recommended article: Asymptotic density, computable traceability, and 1-randomness
Recommended article: On Strongly Equivalent Nonrandomized Transition Probabilities
Recommended article: A random set characterization of possibility measures
review text: Strong jump-traceability was introduced for some very technical reasons. Though the class was known to be a proper subset of \(K\)-trivial sets, it was not clear whether there is a connection between the class and randomness.NEWLINENEWLINEThe authors in the paper under review reveal a significant connection between these notions. They show that c.e. strongly jump-traceable sets are precisely those c.e. sets computable from every superlow random set. Moreover, they are also precisely those c.e. sets computable from every superhigh random set.
description: scientific article; zbMATH DE number 6094112