No CrossRef data available.
Article contents
Comparing the Medvedev and Turing degrees of Π01 classes
Published online by Cambridge University Press: 10 November 2014
Abstract
Every co-c.e. closed set (Π01 class) in Cantor space is represented by a co-c.e. tree. Our aim is to clarify the interaction between the Medvedev and Muchnik degrees of co-c.e. closed subsets of Cantor space and the Turing degrees of their co-c.e. representations. Among other results, we present the following theorems: if v and w are different c.e. degrees, then the collection of the Medvedev (Muchnik) degrees of all Π01 classes represented by v and the collection represented by w are also different; the ideals generated from such collections are also different; the collections of the Medvedev and Muchnik degrees of all Π01 classes represented by incomplete co-c.e. sets are upward dense; the collection of all Π01 classes represented by K-trivial sets is Medvedev-bounded by a single Π01 class represented by an incomplete co-c.e. set; and the Π01 classes have neither nontrivial infinite suprema nor infima in the Medvedev lattice.
- Type
- Paper
- Information
- Mathematical Structures in Computer Science , Volume 25 , Special Issue 8: Computing with Infinite Data: Topological and Logical Foundations Part 2 , December 2015 , pp. 1649 - 1668
- Copyright
- Copyright © Cambridge University Press 2014
References
