Some effects of Ash-Nerode and other decidability conditions on degree spectra (Q1182431): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Rodney G. Downey / 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 / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0168-0072(91)90097-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1975720205 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3919698 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Autostability and computable families of constructivizations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computable single-valued numerations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3931264 / 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: Semirecursive Sets and Positive Reducibility / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Foundations of recursive model theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3819052 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 15:23, 15 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some effects of Ash-Nerode and other decidability conditions on degree spectra |
scientific article |
Statements
Some effects of Ash-Nerode and other decidability conditions on degree spectra (English)
0 references
28 June 1992
0 references
Many examples in recursive algebra/model theory/combinatorics can be viewed as asking when it is possible to find in the isomorphism type of a recursive model \(M\) with a recursive \((\Sigma_ n\), \(\pi_ n\), etc.) relation \(R\) a recursive copy of \(M\) with the image of \(R\) failing to be recursive (resp. \(\Sigma_ n\), \(\pi_ n)\). This question has been extensively studied by Ash, Knight, Moses, Goncharov, Nerode and others. \textit{C. J. Ash} and \textit{A. Nerode} [Aspects of effective algebra, Proc. Conf., Monash Univ. 1979, 26-41 (1981; Zbl 0467.03041)] gave syntactic conditions, which, subject to certain decidability conditions, classified when the answer was ``yes'', i.e., when the relation was ``intrinsically recursive''. Here the author contributes to these studies by a partial classification of the degree spectrum of a relation \(R\). That is, the collection of degrees that can be realized as the degrees of images of \(R\). The author establishes that while it is possible for a recursive nonintrinsically \(\Sigma_ 1\) relation to be a two-element degree spectrum, a nonintrinsically r.e. relation \(R\) that satisfies the Ash- Nerode decidability condition has an infinite degree spectrum. The first result is shown to follow from the difficult construction of \textit{S. S. Goncharov} [Algebra Logika 14, 647-680 (1975; Zbl 0367.02023)] and the second combines an Ash-Nerode construction with a Friedberg-Muchnik one. The author gives a number of examples as to the range of the degree spectrum (particularly in the setting of linear orderings).
0 references
recursive model
0 references
degree spectrum of a relation
0 references
Ash-Nerode decidability condition
0 references