Switch to: Citations

Add references

You must login to add references.
  1. Pseudo-Jump Operators. II: Transfinite Iterations, Hierarchies and Minimal Covers.Carl G. Jockusch & Richard A. Shore - 1984 - Journal of Symbolic Logic 49 (4):1205 - 1236.
  • Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
    We show that for every c.e. degree a > 0 there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. This result can be extended in two directions. First we show that for every uniformly c.e. collection of sets S there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is the set of degrees of elements of S. Then we show that if α ∈ (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Dynamic Notions of Genericity and Array Noncomputability.Benjamin Schaeffer - 1998 - Annals of Pure and Applied Logic 95 (1-3):37-69.
    We examine notions of genericity intermediate between 1-genericity and 2-genericity, especially in relation to the Δ20 degrees. We define a new kind of genericity, dynamic genericity, and prove that it is stronger than pb-genericity. Specifically, we show there is a Δ20 pb-generic degree below which the pb-generic degrees fail to be downward dense and that pb-generic degrees are downward dense below every dynamically generic degree. To do so, we examine the relation between genericity and array noncomputability, deriving some structural information (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Some Effects of Ash–Nerode and Other Decidability Conditions on Degree Spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 55 (1):51-65.
    With every new recursive relation R on a recursive model , we consider the images of R under all isomorphisms from to other recursive models. We call the set of Turing degrees of these images the degree spectrum of R on , and say that R is intrinsically r.e. if all the images are r.e. C. Ash and A. Nerode introduce an extra decidability condition on , expressed in terms of R. Assuming this decidability condition, they prove that R is (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   21 citations  
  • Uncountable Degree Spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 54 (3):255-263.
    We consider a recursive model and an additional recursive relation R on its domain, such that there are uncountably many different images of R under isomorphisms from to some recursive model isomorphic to . We study properties of the set of Turing degrees of all these isomorphic images of R on the domain of.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • On $\Pi^0_1$ Classes and Their Ranked Points.Rod Downey - 1991 - Notre Dame Journal of Formal Logic 32 (4):499-512.
  • Permitting, Forcing, and Copying of a Given Recursive Relation.C. J. Ash, P. Cholak & J. F. Knight - 1997 - Annals of Pure and Applied Logic 86 (3):219-236.
  • Turing Degrees of Certain Isomorphic Images of Computable Relations.Valentina S. Harizanov - 1998 - Annals of Pure and Applied Logic 93 (1-3):103-113.
    A model is computable if its domain is a computable set and its relations and functions are uniformly computable. Let be a computable model and let R be an extra relation on the domain of . That is, R is not named in the language of . We define to be the set of Turing degrees of the images f under all isomorphisms f from to computable models. We investigate conditions on and R which are sufficient and necessary for to (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • Intrinsically Gs;0alpha; Relations.E. Barker - 1988 - Annals of Pure and Applied Logic 39 (2):105-130.
  • Members of Countable Π10 Classes.Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare & Stanley S. Wainer - 1986 - Annals of Pure and Applied Logic 31 (2):145-163.
  • Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures.Walker M. White & Denis R. Hirschfeldt - 2002 - Notre Dame Journal of Formal Logic 43 (1):51-64.
    We construct a class of relations on computable structures whose degree spectra form natural classes of degrees. Given any computable ordinal and reducibility r stronger than or equal to m-reducibility, we show how to construct a structure with an intrinsically invariant relation whose degree spectrum consists of all nontrivial r-degrees. We extend this construction to show that can be replaced by either or.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Computable Structures and the Hyperarithmetical Hierarchy.C. J. Ash - 2000 - Elsevier.
    This book describes a program of research in computable structure theory. The goal is to find definability conditions corresponding to bounds on complexity which persist under isomorphism. The results apply to familiar kinds of structures (groups, fields, vector spaces, linear orderings Boolean algebras, Abelian p-groups, models of arithmetic). There are many interesting results already, but there are also many natural questions still to be answered. The book is self-contained in that it includes necessary background material from recursion theory (ordinal notations, (...)
    Direct download  
     
    Export citation  
     
    Bookmark   25 citations  
  • Hypersimplicity and Semicomputability in the Weak Truth Table Degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
  • Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.
  • Degree Spectra of Relations on Computable Structures in the Presence of Δ02 Isomorphisms.Denis R. Hirschfeldt - 2002 - Journal of Symbolic Logic 67 (2):697 - 720.
    We give some new examples of possible degree spectra of invariant relations on Δ 0 2 -categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a Δ 0 2 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • A Refinement of Lown and Highn for the R.E. Degrees.Jeanleah Mohrherr - 1986 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 32 (1-5):5-12.
  • Intrinsic Reducibilities.Timothy H. McNicholl - 2000 - Mathematical Logic Quarterly 46 (3):393-407.
    Let equation image. We show that for many reducibilities, the requirement that a relation be intrinsically reducible to the α-th jump of a countable mode A has a syntactic equivalent. Furthermore, we show that many reducibilities coincide in such a situation.
    No categories
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation