A Survey of Muchnik and Medvedev degrees

Abstract

We survey the theory of Muchnik (weak) and Medvedev (strong) degrees of subsets of ${}^{\omega }\omega$ with particular attention to the degrees of ${\Pi }_1^0$ subsets of ${}^{\omega }2$. Later sections present proofs, some more complete than others, of the major results of the subject.

70 pages

References in corpus (1)

• Intuitionistic Logic and Muchnik Degrees