The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
From MaRDI portal
Publication:2655138
DOI10.1007/s00153-009-0150-6zbMath1184.03038MaRDI QIDQ2655138
Joshua A. Cole, Takayuki Kihara
Publication date: 22 January 2010
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00153-009-0150-6
03B25: Decidability of theories and sets of sentences
03D30: Other degrees and reducibilities in computability and recursion theory
Related Items
Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes, Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions, Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism, A Survey of Mučnik and Medvedev Degrees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Working below a \(low_ 2\) recursively enumerable degree
- Density of the Medvedev lattice of \(\Pi^0_1\) classes
- Mass Problems and Randomness
- The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
- A splitting theorem for the Medvedev and Muchnik lattices
- An extension of the recursively enumerable Turing degrees
- Extension of embeddings in the computably enumerable degrees