Lowness properties and approximations of the jump
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. Informa...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Artículo publishedVersion |
| Publicado: |
2008
|
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_01680072_v152_n1-3_p51_Figueira https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_01680072_v152_n1-3_p51_Figueira_oai |
| Aporte de: |
| Sumario: | 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. |
|---|