Lowness properties and approximations of the jump

FIGUEIRA, SANTIAGO; NIES, ANDRÉ; STEPHAN, FRANK

Electronic Notes in Theoretical Computer Science

Elsevier

Año: 2006 vol. 143 p. 45 - 57

1571-0661

We study and compare two combinatorial lowness notions: strong jump-traceability and well-approximability of the jump, by strengthening the notion of jump-traceability and ω-r.e. for sets of natural numbers. We prove that there is a strongly jump-traceable set which is not computable, and that if A′ is well-approximable then A is strongly jump-traceable. For r.e. sets, the converse holds as well. We characterize jump-traceability and the corresponding strong variant in terms of Kolmogorov complexity, and we investigate other properties of these lowness notions. © 2005 Elsevier B.V. All rights reserved.