The theory of the recursively enumerable weak truth-table degrees is undecidable

DOI10.2307/2275436zbMATH Open0776.03020OpenAlexW2048614185MaRDI QIDQ4032867FDOQ4032867

Authors: Klaus Ambos-Spies, André Nies, Richard A. Shore 

Publication date: 1 April 1993

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

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

Recommendations

• scientific article; zbMATH DE number 761273
• scientific article; zbMATH DE number 535104
• The undecidability of the Π₄-theory for the r.e. wtt and Turing degrees
• Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices
• scientific article; zbMATH DE number 15488

zbMATH Keywords

semilatticeelementary theoryr.e. wtt-degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Undecidability and degrees of sets of sentences (03D35)

Cites Work

• Classical recursion theory. Vol. II
• Recursively enumerable sets and degrees
• The weak truth table degrees of recursively enumerable sets
• The recursively enumerable degrees have infinitely many one-types
• Strong reducibilities
• Conference in mathematical logic, London 1970

Cited In (26)

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Π₃-theory of the -enumeration degrees is undecidable
• Classes bounded by incomplete sets
• Title not available (Why is that?)
• Splitting theorems in recursion theory
• Weak truth table degrees of structures
• Title not available (Why is that?)
• The last question on recursively enumerable \(m\)-degrees
• THE THEORY OF THE METARECURSIVELY ENUMERABLE DEGREES
• The theory of the \(\alpha \) degrees is undecidable
• Title not available (Why is that?)
• The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations
• Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices
• Every incomplete computably enumerable truth-table degree is branching
• Cupping and noncapping in the r.e. weak truth table and turing degrees
• 1999 European Summer Meeting of the Association for Symbolic Logic
• A Useful Undecidable Theory
• The theory of the polynomial many-one degrees of recursive sets is undecidable
• 1998–99 Annual Meeting of the Association for Symbolic Logic
• Boolean pairs formed by the \(\Delta_ n^ 0\)-sets
• Interpreting \(\mathbb{N}\) in the computably enumerable weak truth table degrees
• Interpreting true arithmetic in the theory of the r.e. truth table degrees
• The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility
• Title not available (Why is that?)
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable

This page was built for publication: The theory of the recursively enumerable weak truth-table degrees is undecidable

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