Characterizing the strongly jump-traceable sets via randomness

DOI10.1016/J.AIM.2012.06.005MaRDI QIDQ456804zbMATH OpenOpenAlexFDO

Authors Noam Greenberg, Denis R. Hirschfeldt, André Nies

Publication date 16 October 2012

Published in Advances in Mathematics (Search for Journal in Brave)

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

randomness strongly jump-traceable sets superlowness

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

Abstract: We show that if a set

A

is computable from every superlow 1-random set, then

A

is strongly jump-traceable. This theorem shows that the computably enumerable (c.e.) strongly jump-traceable sets are exactly the c.e. sets computable from every superlow 1-random set. We also prove the analogous result for superhighness: a c.e. set is strongly jump-traceable if and only if it is computable from every superhigh 1-random set. Finally, we show that for each cost function

c

with the limit condition there is a 1-random

D e l t a_{2}^{0}

set

Y

such that every c.e. set

A l e_{T} Y

obeys

c

. To do so, we connect cost function strength and the strength of randomness notions. This result gives a full correspondence between obedience of cost functions and being computable from

D e l t a_{2}^{0}

1-random sets.

Recommendations

Cites work

Cited in

(18)

This page was built for publication: Characterizing the strongly jump-traceable sets via randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456804)