The last question on recursively enumerable \(m\)-degrees

DOI10.1007/BF00739571zbMath0846.03017OpenAlexW2034985264MaRDI QIDQ1908450

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

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

Related Items

Interpreting true arithmetic in the theory of the r.e. truth table degrees, Coding in the partial order of enumerable sets, The theory of ceers computes true arithmetic, Elementary theories and hereditary undecidability for semilattices of numberings, Interpreting true arithmetic in the local structure of the enumeration degrees, Computably enumerable sets and related issues, Effectively dense Boolean algebras and their applications

Cites Work

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