The last question on recursively enumerable m-degrees

DOI10.1007/BF00739571MaRDI QIDQ1908450zbMATH OpenOpenAlexFDO

Authors André Nies

Publication date 19 March 1996

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/187699

zbMATH Keywords

computational complexityfirst-order arithmeticrecursively enumerable \(m\)-degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15) Models of arithmetic and set theory (03C62)

Recommendations

• Interpreting true arithmetic in the theory of the r.e. truth table degrees
• scientific article; zbMATH DE number 517082
• THE THEORY OF THE METARECURSIVELY ENUMERABLE DEGREES

Cites work

• Classical recursion theory. The theory of functions and sets of natural numbers
• Interpreting true arithmetic in the theory of the r.e. truth table degrees
• Model theory of the computably enumerable many-one degrees
• The Theory of the Degrees below 0 ′
• The computable enumerations of families of general recursive functions
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• The undecidability of the recursively enumerable degrees
• Undecidable fragments of elementary theories

Cited in

(15)

• Interpreting true arithmetic in the theory of the r.e. truth table degrees
• Manifolds allowing RET arithmetic
• The theory of ceers computes true arithmetic
• scientific article; zbMATH DE number 5000253 (Why is no real title available?)
• Elementary theories and hereditary undecidability for semilattices of numberings
• Interpreting true arithmetic in the local structure of the enumeration degrees
• Effectively dense Boolean algebras and their applications
• Model theory of the computably enumerable many-one degrees
• Coding in the partial order of enumerable sets
• scientific article; zbMATH DE number 3977006 (Why is no real title available?)
• scientific article; zbMATH DE number 1531918 (Why is no real title available?)
• Why the theory R is special
• Computably enumerable sets and related issues
• scientific article; zbMATH DE number 2236629 (Why is no real title available?)
• scientific article; zbMATH DE number 517082 (Why is no real title available?)

This page was built for publication: The last question on recursively enumerable \(m\)-degrees

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