Some effects of Ash–Nerode and other decidability conditions on degree spectra

Annals of Pure and Applied Logic 55 (1):51-65 (1991)

Authors
Valentina Harizanov
George Washington University
Abstract
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 intrinsically r.e. if and only if a natural recursive-syntactic condition is satisfied. We show that, while a recursive non-intrinsically r.e. relation may have a two element degree spectrum, a non-intrinsically r.e. relation which satisfies the Ash–Nerode decidability condition has an infinite degree spectrum. We also study several related decidability conditions and their effects on the degree spectra, including some conditions which are sufficient to obtain every r.e. degree in a spectrum
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(91)90097-6
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,940
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Uncountable Degree Spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 54 (3):255-263.
Foundations of Recursive Model Theory.Terrence S. Millar - 1978 - Annals of Pure and Applied Logic 13 (1):45.

Add more references

Citations of this work BETA

Turing Degrees of Certain Isomorphic Images of Computable Relations.Valentina S. Harizanov - 1998 - Annals of Pure and Applied Logic 93 (1-3):103-113.

View all 21 citations / Add more citations

Similar books and articles

Uncountable Degree Spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 54 (3):255-263.
Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - Journal of Symbolic Logic 72 (1):324 - 348.
Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
Jack and Jill Have Shifted Spectra.Ned Block - 1999 - Behavioral and Brain Sciences 22 (6):946-947.
Approximate Decidability in Euclidean Spaces.Armin Hemmerling - 2003 - Mathematical Logic Quarterly 49 (1):34-56.
Decidability of an Xstit Logic.Gillman Payette - 2014 - Studia Logica 102 (3):577-607.
The Degree Spectra of Homogeneous Models.Karen Lange - 2008 - Journal of Symbolic Logic 73 (3):1009-1028.

Analytics

Added to PP index
2014-01-16

Total views
6 ( #885,999 of 2,235,424 )

Recent downloads (6 months)
5 ( #363,176 of 2,235,424 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature