کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430205 | 687926 | 2016 | 17 صفحه PDF | دانلود رایگان |
• 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.
Journal: Journal of Computer and System Sciences - Volume 82, Issue 8, December 2016, Pages 1283–1299