The possible Turing degree of the nonzero member in a two element degree spectrum (Q1210135): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Set OpenAlex properties.
 
(5 intermediate revisions by 4 users not shown)
Property / reviewed by
 
Property / reviewed by: Rodney G. Downey / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Rodney G. Downey / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Stability of recursive structures in arithmetical degrees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computable single-valued numerations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Problem of the number of non-self-equivalent constructivizations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3331204 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Uncountable degree spectra / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some effects of Ash-Nerode and other decidability conditions on degree spectra / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4040892 / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0168-0072(93)90190-o / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2032686575 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 09:22, 30 July 2024

scientific article
Language Label Description Also known as
English
The possible Turing degree of the nonzero member in a two element degree spectrum
scientific article

    Statements

    The possible Turing degree of the nonzero member in a two element degree spectrum (English)
    0 references
    16 May 1993
    0 references
    Ash and Nerode defined a recursive relation \(R\) on a recursive model \(A\) to be intrinsically recursive if in each recursive model \(B\) isomorphic to \(A\), the image of \(R\) is recursive. Not all relations \(R\) are intrinsically recursive, and in this paper the author continues her studies into the degree spectrum of such \(R\). The degree spectrum of \(R\) is the collection of Turing degrees realised by the images of \(R\). Such spectra can have uncountably many members, but can have other realisations. In an earlier paper [ibid. 55, No. 1, 51-65 (1991; Zbl 0756.03022)], the author established that there is a two-element degree spectrum whose nonzero degree can be realised by a \(\Delta_ 3^ 0- \Delta_ 2^ 0\) set. The present paper improves this to \(\Delta_ 2^ 0-\Sigma_ 1\). This is established via a technical result constructing a recursive family of r.e. sets with exactly two 1-1 recursive enumerations up to equivalence. This technical result is proven to quite an elaborate argument constituting the bulk of the paper and is of independent interest. Both this argument and the main result are modifications of an earlier argument of \textit{S. S. Goncharov} [Algebra Logika 19, 507-551 (1980; Zbl 0514.03029)].
    0 references
    intrinsically recursive relation
    0 references
    recursive model
    0 references
    degree spectrum
    0 references
    Turing degrees
    0 references
    recursive family of r.e. sets
    0 references

    Identifiers