Decidability and Invariant Classes for Degree Structures

DOI10.2307/2000985zbMATH Open0707.03036OpenAlexW4233434551MaRDI QIDQ3487331FDOQ3487331

Authors: Richard A. Shore, Manuel Lerman 

Publication date: 1988

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

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

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)

Cites Work

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

Cited In (19)

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

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)