کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430205 687926 2016 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
چکیده انگلیسی


• Optimal oracle-use of Chaitin's Omega number.
• Qualification and optimization of the completeness of Chaitin's Omega.
• Tight bounds on oracle use in the computably enumerable sets and reals.

We characterise the asymptotic upper bounds on the use of Chaitin's Ω in oracle computations of halting probabilities (i.e. c.e. reals). We show that the following two conditions are equivalent for any computable function h   such that h(n)−nh(n)−n is non-decreasing: (1) h(n)−nh(n)−n is an information content measure, i.e. the series ∑n2n−h(n)∑n2n−h(n) converges, (2) for every c.e. real α there exists a Turing functional via which Ω computes α with use bounded by h. We also give a similar characterisation with respect to computations of c.e. sets from Ω, by showing that the following are equivalent for any computable non-decreasing function g: (1) g is an information-content measure, (2) for every c.e. set A, Ω computes A with use bounded by g. Further results and some connections with Solovay functions (studied by a number of authors [38], [3], [26] and [11]) are given.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 82, Issue 8, December 2016, Pages 1283–1299
نویسندگان
, , ,