The n-r.e. degrees: undecidability and _1 substructures
The \(n\)-r.e. degrees: undecidability and \(\Sigma 1\) substructures
A recursive function \(f(x,s)\) approximates the set \(A\) if for all \(x\), \(f(x,0)=0\), \(\lim_s f(x,s) \in \{0,1\}\), and \(\lim_s f(x,s) = 1\) if and only if \(x \in A\). The \(n\)-r.e.~sets are those which have a recursive approximation with at most \(n\) changes of value for each \(x\). Thus, the \(1\)-r.e.~sets are the familiar recursively enumerable sets. The \(n\)-r.e.~sets are also called \(n\)-c.e.~in the literature, and arise from the \(n\)-trial predicates of \textit{H. Putnam} [``Trial and error predicates and the solution to a problem of Mostowski, J. Symb. Log. 30, 49--57 (1965; Zbl 0193.30102)]. This paper addresses the global properties of \(\mathcal D_n\), the Turing degrees of the \(n\)-r.e.~sets, showing that the structure of each \(\mathcal D_n\) is very complicated. In particular, the authors prove (1) for every \(n\) the theory of \(\mathcal D_n\) is undecidable, and (2) if \(n<m\) then \(\mathcal D_n\) is not a \(\Sigma_1\)-substructure of \(\mathcal D_m\).
- A minimal pair of recursively enumerable degrees
- D.R.E. Degrees and the Nondiamond Theorem
- Degree Structures: Local and Global Investigations
- Degrees of unsolvability: structure and theory
- DIRECT AND LOCAL DEFINITIONS OF THE TURING JUMP
- Distributive Initial Segments of the Degrees of Unsolvability
- First-order theory of the degrees of recursive unsolvability
- Interpretability and Definability in the Recursively Enumerable Degrees
- Limiting recursion
- On a hierarchy of sets. III
- On degrees of unsolvability
- On Downey's conjecture
- On Σ1-Structural Differences Among Finite Levels of the Ershov Hierarchy
- Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
- The d.r.e. degrees are not dense
- The undecidability of the recursively enumerable degrees
- Undecidability of local structures of s-degrees and Q-degrees
- Intervals and sublattices of the r.e. weak truth table degrees. II: Nonbounding
- Some effects of Ash-Nerode and other decidability conditions on degree spectra
- The undecidability of some equivalence problems concerning ngsm's and finite substitutions
- Isolated maximal d.r.e. degrees
- Matrix hierarchies of first-order languages and their applications
- Weak density and nondensity among transfinite levels of the Ershov hierarchy
- Turing computability: structural theory
- Isolation from side in 2-computably enumerable degrees
- A survey of results on the d.c.e. and \(n\)-c.e. degrees
- scientific article; zbMATH DE number 3857081 (Why is no real title available?)
- Representation of One-One Degrees byn-Cylindrical Decision Problems
- scientific article; zbMATH DE number 22854 (Why is no real title available?)
- The discrete parts of approximately decidable sets in Euclidean spaces
- scientific article; zbMATH DE number 761273 (Why is no real title available?)
- Extending properly n - REA sets1
- The \(\forall\exists\) theory of \({\mathcal D}(\leq,\vee,{}')\) is undecidable
- An undecidable linear order that is \(n\)-decidable for all \(n\)
- The theory of the degrees is undecidable
- Isolation from side and cone avoidance in the 2-computably enumerable \textit{wtt}-degrees
- Undecidability of the structure of the Solovay degrees of c.e. reals
This page was built for publication: The \(n\)-r.e. degrees: undecidability and \(\Sigma_1\) substructures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909622)
