Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950585 | Information and Computation | 2017 | 11 Pages |
Abstract
We look at the question of join preservation for bounded Turing reducibilities r and râ² such that r is stronger than râ². We say that join preservation holds for two reducibilities r and râ² if every join in the computably enumerable (c.e.) r-degrees is also a join in the c.e. râ²-degrees. We consider the class of monotone admissible (uniformly) bounded Turing reducibilities, i.e. the reflexive and transitive Turing reducibilities with use bounded by a function that is contained in a (uniformly computable) family of strictly increasing computable functions. This class contains for example identity bounded Turing (ibT-) and computable Lipschitz (cl-) reducibility. Our main result is that join preservation fails for cl and any strictly weaker monotone admissible uniformly bounded Turing reducibility (Theorem 10). We also look at the dual question of meet preservation and show that for all monotone admissible bounded Turing reducibilities r and râ² such that r is stronger than râ², meet preservation holds. Finally, we completely solve the question of join and meet preservation in the classical reducibilities 1, m, tt, wtt, and T. This is an extended version of our article [18].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nadine Losert,