کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950585 1440713 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Where join preservation fails in the bounded Turing degrees of c.e. sets
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Where join preservation fails in the bounded Turing degrees of c.e. sets
چکیده انگلیسی
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].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 256, October 2017, Pages 185-195
نویسندگان
,