Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.apal.2007.11.002
Title: Lowness properties and approximations of the jump
Authors: Figueira, S.
Nies, A.
Stephan, F. 
Keywords: ω-r.e.
K-triviality
Kolmogorov complexity
Lowness
Traceability
Issue Date: Mar-2008
Citation: Figueira, S., Nies, A., Stephan, F. (2008-03). Lowness properties and approximations of the jump. Annals of Pure and Applied Logic 152 (1-3) : 51-66. ScholarBank@NUS Repository. https://doi.org/10.1016/j.apal.2007.11.002
Abstract: 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 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 Te of possible values for the jump JA (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. © 2007 Elsevier B.V. All rights reserved.
Source Title: Annals of Pure and Applied Logic
URI: http://scholarbank.nus.edu.sg/handle/10635/104502
ISSN: 01680072
DOI: 10.1016/j.apal.2007.11.002
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

22
checked on Mar 31, 2020

WEB OF SCIENCETM
Citations

18
checked on Mar 23, 2020

Page view(s)

53
checked on Mar 28, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.