A survey of Mučnik and Medvedev degrees

DOI10.2178/BSL/1333560805MaRDI QIDQ2893281zbMATH OpenOpenAlexFDO

Authors Peter G. Hinman

Publication date 20 June 2012

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.2376, https://projecteuclid.org/euclid.bsl/1333560805

zbMATH Keywords

survey paperMedvedev degreeimplicative latticesMuchnik degree\(\Pi^0_1\) sets and classesglobal degree structureslattice logicslocal degree structures

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Abstract: We survey the theory of Muchnik (weak) and Medvedev (strong) degrees of subsets of ${}^{o}megaomega$ with particular attention to the degrees of $P{i}_1^0$ subsets of ${}^{o}mega2$. Later sections present proofs, some more complete than others, of the major results of the subject.

Recommendations

• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Comparing the Medvedev and Turing degrees of \(\Pi^{0}_{1}\) classes
• scientific article; zbMATH DE number 841094
• Coding true arithmetic in the Medvedev degrees of ^0_1 classes
• Coding true arithmetic in the Medvedev and Muchnik degrees

Cites work

• scientific article; zbMATH DE number 3577197 (Why is no real title available?)
• scientific article; zbMATH DE number 5264766 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 2232435 (Why is no real title available?)
• A fixed-point-free minimal degree
• A splitting theorem for the Medvedev and Muchnik lattices
• Algorithmic randomness and complexity.
• Almost everywhere domination
• An extension of the recursively enumerable Turing degrees
• Class groups of integral group rings
• Coding true arithmetic in the Medvedev and Muchnik degrees
• Computability and randomness
• Degrees of difficulty of generalized r.e. separating classes
• Degrees of models
• Density of the Medvedev lattice of \(\Pi^0_1\) classes
• Embedding Brouwer algebra in the Medvedev lattice
• Embedding \(\mathrm{FD}(\omega)\) into \({\mathcal{P}_s}\) densely
• Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
• Intermediate logics and factors of the Medvedev lattice
• K-Triviality of Closed Sets and Continuous Functions
• Mass Problems and Randomness
• Mass problems and intuitionism
• On the structure of the Medvedev lattice
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• Some Quotient Lattices of the Medvedev Lattice
• Some remarks on the algebraic structure of the Medvedev Lattice
• The First Order Theories of the Medvedev and Muchnik Lattices
• The Medvedev lattice of computably closed sets
• The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
• The definition of random sequences

Cited in

(18)

• Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
• Completeness, Compactness, Effective Dimensions
• A survey of results on the d.c.e. and \(n\)-c.e. degrees
• Minimal covers in the Weihrauch degrees
• Computability of Subsets of Metric Spaces
• Randomness notions and reverse mathematics
• Comparing the Medvedev and Turing degrees of \(\Pi^{0}_{1}\) classes
• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Highness properties close to PA completeness
• Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes
• First-order logic in the Medvedev lattice
• Feedback computability on Cantor space
• Natural factors of the Muchnik lattice capturing IPC
• Medvedev degrees of generalized r.e. separating classes
• Coding true arithmetic in the Medvedev and Muchnik degrees
• Natural factors of the Medvedev lattice capturing IPC
• Comparing the degrees of enumerability and the closed Medvedev degrees
• Medvedev degrees of two-dimensional subshifts of finite type

This page was built for publication: A survey of Mučnik and Medvedev degrees

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