scientific article; zbMATH DE number 761273

MaRDI QIDQ4835608zbMATH OpenFDO

Authors Richard A. Shore

Publication date 3 July 1995

zbMATH Keywords

algebraic structureautomorphismscomplexity of the decision proceduredefinabilitydensitydistributivityembeddings of partial orderingsinfimalatticesrecursively enumerable setstruth-table reducibilityTuring reducibilityundecidabilityupper semilatticeweak truth-table reducibility

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• The undecidability of the Π₄-theory for the r.e. wtt and Turing degrees
• Undecidability and initial segments of the (r.e.) tt-degrees
• The \(n\)-r.e. degrees: undecidability and \(\Sigma_1\) substructures
• scientific article; zbMATH DE number 15488
• Decidability and undecidability in the enumerable Turing degrees
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• Definability issues in the -Turing degrees
• The \(\omega\)-Turing degrees
• Alfred Tarski and undecidable theories

Cited in

(11)

• Structural interactions of the recursively enumerable T- and W-degrees
• Intervals and sublattices of the r.e. weak truth table degrees. I: Density
• Tabular degrees in \(\alpha\)-recursion theory
• Structure of the semilattice of tt1-degrees
• Interpreting true arithmetic in the theory of the r.e. truth table degrees
• scientific article; zbMATH DE number 3857082 (Why is no real title available?)
• scientific article; zbMATH DE number 4053595 (Why is no real title available?)
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• scientific article; zbMATH DE number 1048044 (Why is no real title available?)
• Undecidability and initial segments of the (r.e.) tt-degrees
• Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices

This page was built for publication:

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