Decidability and Invariant Classes for Degree Structures

DOI10.2307/2000985MaRDI QIDQ3487331zbMATH OpenOpenAlexFDO

Authors Richard A. Shore, Manuel Lerman

Publication date 1988

Full work available at URL https://doi.org/10.2307/2000985

zbMATH Keywords

decision procedureinitial segmentjump classesextension of embeddings\(\forall \exists \)-theoryTuring degrees below \(\underset\sim 0^{\prime }\)

Mathematics Subject Classification ID

Hierarchies of computability and definability (03D55) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• There is no ordering on the classes in the generalized high/low hierarchies
• The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations
• Embedding jump upper semilattices into the Turing degrees
• Degree invariance in the \(\Pi ^{0}_{1}\) classes
• Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices

Cites work

• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 3941523 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• A minimal degree not realizing least possible jump
• Defining Jump Classes in the Degrees Below 0'
• Degrees joining to 0′
• Degrees which do not bound minimal degrees
• Distributive Initial Segments of the Degrees of Unsolvability
• Double jumps of minimal degrees
• Initial segments of degrees below 0′
• Initial segments of the degrees of unsolvability
• Initial segments of the degrees of unsolvability Part II: minimal degrees
• Jump restricted interpolation in the recursively enumerable degrees
• Simple Proofs of Some Theorems on High Degrees of Unsolvability
• The Theory of the Degrees below 0 ′
• The upper semi-lattice of degrees of recursive unsolvability

Cited in

(20)

• Degree invariance in the \(\Pi ^{0}_{1}\) classes
• The \(\forall\exists\) theory of \({\mathcal D}(\leq,\vee,{}')\) is undecidable
• Turing computability: structural theory
• There is no ordering on the classes in the generalized high/low hierarchies
• Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)
• Preservation and decomposition theorems for bounded degree structures
• scientific article; zbMATH DE number 4161543 (Why is no real title available?)
• Some effects of Ash-Nerode and other decidability conditions on degree spectra
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• Classes of Tree Homomorphisms with Decidable Preservation of Regularity
• A non-inversion theorem for the jump operator
• Fragments of the theory of the enumeration degrees
• Degree-invariant, analytic equivalence relations without perfectly many classes
• Extensions of embeddings below computably enumerable degrees
• The Σ 2 theory of D h ( ⩽ h O ) as an uppersemilattice with least and greatest element is decidable
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
• On the decidability of the \(\Sigma_2\) theories of the arithmetic and hyperarithmetic degrees as uppersemilattices
• Homomorphisms and quotients of degree structures
• The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations
• scientific article; zbMATH DE number 3941523 (Why is no real title available?)

This page was built for publication: Decidability and Invariant Classes for Degree Structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3487331)