Decidability and Invariant Classes for Degree Structures
From MaRDI portal
Publication:3487331
DOI10.2307/2000985zbMath0707.03036OpenAlexW4233434551MaRDI QIDQ3487331
Richard A. Shore, Manuel Lerman
Publication date: 1988
Full work available at URL: https://doi.org/10.2307/2000985
decision procedureinitial segmentjump classesextension of embeddings\(\forall \exists \)-theoryTuring degrees below \(\underset\sim 0^{\prime }\)
Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55)
Related Items
The Σ 2 theory of D h ( ⩽ h O ) as an uppersemilattice with least and greatest element is decidable ⋮ The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ A non-inversion theorem for the jump operator ⋮ Homomorphisms and quotients of degree structures ⋮ The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory ⋮ Fragments of the theory of the enumeration degrees ⋮ Turing computability: structural theory ⋮ Extensions of embeddings below computably enumerable degrees
Cites Work
- Degrees which do not bound minimal degrees
- Initial segments of the degrees of unsolvability
- Jump restricted interpolation in the recursively enumerable degrees
- The upper semi-lattice of degrees of recursive unsolvability
- Degrees joining to 0′
- Defining Jump Classes in the Degrees Below 0'
- The Theory of the Degrees below 0 ′
- Initial segments of degrees below 0′
- A minimal degree not realizing least possible jump
- Simple Proofs of Some Theorems on High Degrees of Unsolvability
- Double jumps of minimal degrees
- Distributive Initial Segments of the Degrees of Unsolvability
- Initial segments of the degrees of unsolvability Part II: minimal degrees
- Unnamed Item
- Unnamed Item
- Unnamed Item