Lowness Properties and Approximations of the Jump
| dc.contributor.author | FIGUEIRA, Santiago | en_US |
| dc.contributor.author | NIES, Andre | en_US |
| dc.contributor.author | STEPHAN, Frank | en_US |
| dc.date.accessioned | 2005-11-14T07:18:55Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:01Z | |
| dc.date.available | 2005-11-14T07:18:55Z | en_US |
| dc.date.available | 2017-01-23T07:00:01Z | |
| dc.date.issued | 2005-11-10 | en_US |
| dc.description.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 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 the corresponding strong variant in terms of Kolmogorov complexity, and we investigate other properties of these lowness ... | en_US |
| dc.format.extent | 481019 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1863 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TR11/05 | en_US |
| dc.title | Lowness Properties and Approximations of the Jump | en_US |
| dc.type | Technical Report | en_US |