Lowness properties and approximations of the jump

SANTIAGO FIGUEIRA; ANDRÉ NIES; FRANK STEPHAN

ANNALS OF PURE AND APPLIED LOGIC

Elsevier

Año: 2008 vol. 152 p. 51 - 66

0168-0072

We study and compare two combinatorial lowness notions: "trong jump-traceability" and "well-approximability of the jump", by strengthening the notion of jumptraceability and super-lowness for sets of natural numbers. A computable non-decreasing unbounded function h is called an order function. Informally, a set A is strongly jump traceable if for each order function h, for each input e one may effectively enumerate a set T_e of possible values for the jump J^A(e), and the number of values enumerated is at most h(e). A´ is well approximable if can be effectively approximated with less than h(x) changes at input x, for each order function h. 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 strong jump-traceability  in terms of Kolmogorov complexity. We also investigate other properties of these lowness properties.