Possible degrees in recursive copies (Q1902615)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Possible degrees in recursive copies |
scientific article |
Statements
Possible degrees in recursive copies (English)
0 references
13 May 1996
0 references
A recursive structure is a recursive set \(A\) together with recursive relations \(R\) on \(A\). We denote this \((A, R)\). It is of interest to know if there are isomorphic structures (called `recursive copies') \((A', R')\) where \(A'\) is recursive but \(R'\) is not. More generally, the degree spectra of \((A, R)\) is the set of Turing degrees \({\mathbf a}\) such that there is some recursive copy \((A', R')\) where \(R'\) has degree \({\mathbf a}\). \textit{V. S. Harizanov} [Ann. Pure Appl. Log. 55, 51-65 (1991; Zbl 0756.03022)] has isolated a syntactic condition (with additional effectiveness conditions) which is necessary and sufficient for \((A, R)\) to have degree spectra all the r.e. degrees. It is an open question to determine a condition under which the degree spectra is all the \(\Sigma_\alpha\) degrees. This paper shows that several conjectures of conditions are false.
0 references
recursive structure
0 references
isomorphic structures
0 references
Turing degrees
0 references
recursive copy
0 references
degree spectra
0 references