Please use this identifier to cite or link to this item:
|Title:||Lowness properties and approximations of the jump||Authors:||Figueira, S.
|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.
checked on Mar 31, 2020
WEB OF SCIENCETM
checked on Mar 23, 2020
checked on Mar 28, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.