کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662776 1633534 2008 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Lowness properties and approximations of the jump
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Lowness properties and approximations of the jump
چکیده انگلیسی

We study and compare two combinatorial lowness notions: strong jump-traceability and well-approximability of the jump, by strengthening the notion of jump-traceability and super-lowness for sets of natural numbers. A computable non-decreasing unbounded function h is called an order function. Informally, a set A is strongly jump-traceable if for each order function h, for each input e one may effectively enumerate a set Te of possible values for the jump JA(e), and the number of values enumerated is at most h(e). A′ is well-approximable if can be effectively approximated with less than h(x) changes at input x, for each order function h. We prove that there is a strongly jump-traceable set which is not computable, and that if A′ is well-approximable then A is strongly jump-traceable. For r.e. sets, the converse holds as well. We characterize jump-traceability and strong jump-traceability in terms of Kolmogorov complexity. We also investigate other properties of these lowness properties.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 152, Issues 1–3, March 2008, Pages 51-66