Artículo
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.
Registro:
| Documento: | Artículo |
| Título: | Lowness properties and approximations of the jump |
| Autor: | Figueira, S.; Nies, A.; Stephan, F. |
| Filiación: | Departamento de Computación, FCEyN, Universidad de Buenos Aires, Pabellon I, Ciudad Universitaria, C1428EGA Buenos Aires, Argentina Department of Computer Science, University of Auckland, Building 303, 38 Princes Street, Auckland, New Zealand School of Computing, National University of Singapore, 3 Science Drive 2, Singapore, 117543, Singapore |
| Palabras clave: | ω-r.e.; K-triviality; Kolmogorov complexity; Lowness; Traceability |
| Año: | 2008 |
| Volumen: | 152 |
| Número: | 1-3 |
| Página de inicio: | 51 |
| Página de fin: | 66 |
| DOI: | http://dx.doi.org/10.1016/j.apal.2007.11.002 |
| Título revista: | Annals of Pure and Applied Logic |
| Título revista abreviado: | Ann. Pure Appl. Logic |
| ISSN: | 01680072 |
| CODEN: | APALD |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/paper/paper_01680072_v152_n1-3_p51_Figueira.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01680072_v152_n1-3_p51_Figueira |
Referencias:
- Mark Bickford, Charlie F. Mills, Lowness properties of r.e. sets, Manuscript, UW Madison, 1982; Chaitin, G., A theory of program size formally identical to information theory (1975) Journal of the Association for Computing Machinery, 22, pp. 329-340
- Chaitin, G., Information-theoretical characterizations of recursive infinite strings (1976) Theoretical Computer Science, 2, pp. 45-48
- Peter Cholak, Rod Downey, Noam Greenberg, Strongly jump-traceability I: The computably enumerable case, Advances in Mathematics (in press); Downey, R., Hirschfeldt, D., Miller, J., Nies, A., Relativizing Chaitin's halting probability (2005) Journal of Mathematical Logic, 5 (2), pp. 167-192
- Downey, R., Hirschfeldt, D., Nies, A., Stephan, F., Trivial reals (2003) Proceedings of the 7th and 8th Asian Logic Conferences, pp. 103-131. , World Scientific, River Edge, NJ
- Figueira, S., Stephan, F., Wu, G., Randomness and universal machines (2005) Informatik Berichte, 326, pp. 103-116. , CCA 2005, Second International Conference on Computability and Complexity in Analysis, Fernuniversität Hagen
- Li, M., Vitányi, P., (1997) An Introduction to Kolmogorov Complexity and its Applications. second ed., , Springer, Heidelberg
- Mohrherr, J., A refinement of low n and high n for the r.e. degrees (1986) Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 32 (1), pp. 5-12
- Nies, A., Lowness properties and randomness (2005) Advances in Mathematics, 197, pp. 274-305
- Nies, A., Reals which compute little (2002) Lecture Notes in Logic, 27, pp. 261-275. , Proceedings of Logic Colloquium 2002. Chatzidakis Z., Koepke P., and Pohlers W. (Eds)
- Odifreddi, P., (1989) Classical Recursion Theory, 1. , North-Holland, Amsterdam vol. 2, Elsevier, Amsterdam 1999
- Terwijn, S., Zambella, D., Algorithmic randomness and lowness (2001) The Journal of Symbolic Logic, 66, pp. 1199-1205
Citas:
---------- APA ----------
Figueira, S., Nies, A. & Stephan, F. (2008) . Lowness properties and approximations of the jump. Annals of Pure and Applied Logic, 152(1-3), 51-66.http://dx.doi.org/10.1016/j.apal.2007.11.002
---------- CHICAGO ----------
Figueira, S., Nies, A., Stephan, F. "Lowness properties and approximations of the jump" . Annals of Pure and Applied Logic 152, no. 1-3 (2008) : 51-66.http://dx.doi.org/10.1016/j.apal.2007.11.002
---------- MLA ----------
Figueira, S., Nies, A., Stephan, F. "Lowness properties and approximations of the jump" . Annals of Pure and Applied Logic, vol. 152, no. 1-3, 2008, pp. 51-66.http://dx.doi.org/10.1016/j.apal.2007.11.002
---------- VANCOUVER ----------
Figueira, S., Nies, A., Stephan, F. Lowness properties and approximations of the jump. Ann. Pure Appl. Logic. 2008;152(1-3):51-66.http://dx.doi.org/10.1016/j.apal.2007.11.002
