Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China.Victoria Univ Wellington, Sch Math Stat & Operat Res, Wellington, New Zealand. [Fang, Nan] Heidelberg Univ, Inst Informat, D-69115 Heidelberg, Germany. [Lewis-Pye, Andrew] London Sch Econ, Dept Math, Columbia House,Houghton St, London WC2A 2AE, England.
Abstract:
We characterise the asymptotic upper bounds on the use of Chaitin's Omega 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) - n is non decreasing: (1) h(n) - n is an information content measure, i.e. the series Sigma(n) 2(n-h(n)) converges, (2) for every c.e. real alpha there exists a Turing functional via which Omega computes alpha with use bounded by h. We also give a similar characterisation with respect to computations of c.e. sets from Omega, 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, Omega computes A with use bounded by g. Further results and some connections with Solovay functions (studied by a number of authors [38,3,26,11]) are given. (C) 2016 Elsevier Inc. All rights reserved.
English Abstract:
We characterise the asymptotic upper bounds on the use of Chaitin's Omega 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) - n is non decreasing: (1) h(n) - n is an information content measure, i.e. the series Sigma(n) 2(n-h(n)) converges, (2) for every c.e. real alpha there exists a Turing functional via which Omega computes alpha with use bounded by h. We also give a similar characterisation with respect to computations of c.e. sets from Omega, 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, Omega computes A with use bounded by g. Further results and some connections with Solovay functions (studied by a number of authors [38,3,26,11]) are given. (C) 2016 Elsevier Inc. All rights reserved.
Barmpalias, G,Fang, N,Lewis-Pye, A. Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES,2016-01-01,82(8):1283-1299.
