A survey of Mučnik and Medvedev degrees

DOI10.2178/BSL/1333560805zbMATH Open1248.03063arXiv1007.2376OpenAlexW2070956093MaRDI QIDQ2893281FDOQ2893281

Authors: Peter G. Hinman 

Publication date: 20 June 2012

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

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.

Full work available at URL: https://arxiv.org/abs/1007.2376

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 \(\Pi^0_1\) classes
• Coding true arithmetic in the Medvedev and Muchnik degrees

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)

Cites Work

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

Cited In (18)

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

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)