Lowness properties and approximations of the jump

Annals of Pure and Applied Logic 152 (1):51-66 (2008)
  Copy   BIBTEX

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, and the number of values enumerated is at most h. A′ is well-approximable if can be effectively approximated with less than h 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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Benign cost functions and lowness properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
Badness and jump inversion in the enumeration degrees.Charles M. Harris - 2012 - Archive for Mathematical Logic 51 (3-4):373-406.
Limit lemmas and jump inversion in the enumeration degrees.Evan J. Griffiths - 2003 - Archive for Mathematical Logic 42 (6):553-562.
The jump operation for structure degrees.V. Baleva - 2005 - Archive for Mathematical Logic 45 (3):249-265.
Approximations and truth spaces.Jean-Pierre Marquis - 1991 - Journal of Philosophical Logic 20 (4):375 - 401.
Superhighness.Bjørn Kjos-Hanssen & Andrée Nies - 2009 - Notre Dame Journal of Formal Logic 50 (4):445-452.
On the jump classes of noncuppable enumeration degrees.Charles M. Harris - 2011 - Journal of Symbolic Logic 76 (1):177 - 197.
A jump inversion theorem for the enumeration jump.I. N. Soskov - 2000 - Archive for Mathematical Logic 39 (6):417-437.
Lowness and Π₂⁰ nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044-1052.
Lowness for the class of Schnorr random sets.B. Kjös-Hanssen, A. Nies & F. Stephan - 2005 - Notre Dame Journal of Formal Logic 35 (3):647-657.
Lowness for genericity.Liang Yu - 2006 - Archive for Mathematical Logic 45 (2):233-238.

Analytics

Added to PP
2013-12-26

Downloads
36 (#385,000)

6 months
3 (#445,838)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Randomness and computability: Open questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
Mass problems and hyperarithmeticity.Joshua A. Cole & Stephen G. Simpson - 2007 - Journal of Mathematical Logic 7 (2):125-143.
Demuth randomness and computational complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
Benign cost functions and lowness properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
On strongly jump traceable reals.Keng Meng Ng - 2008 - Annals of Pure and Applied Logic 154 (1):51-69.

View all 12 citations / Add more citations

References found in this work

[Omnibus Review].Rod Downey - 1997 - Journal of Symbolic Logic 62 (3):1048-1055.
Computational randomness and lowness.Sebastiaan A. Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.
Computability. An Introduction to Recursive Function Theory.H. B. Enderton - 1987 - Journal of Symbolic Logic 52 (1):292-293.
A Refinement of Low n_ and High _n for the R.E. Degrees.Jeanleah Mohrherr - 1986 - Mathematical Logic Quarterly 32 (1-5):5-12.

View all 6 references / Add more references