Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega

ISCAS OpenIR

	Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
	Barmpalias, G; Fang, N; Lewis-Pye, A
	2016
发表期刊	JOURNAL OF COMPUTER AND SYSTEM SCIENCES
ISSN	0022-0000
卷号	82 期号:8 页码:1283-1299
摘要	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.; 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.
收录类别	SCI
关键词	Halting Probability Oracle Use Oracles Optimal Asymptotic Kolmogorov Completeness Computability Complexity
部门归属	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.
语种	英语
WOS记录号	WOS:000380383700005
引用统计
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/17291
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	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,82(8):1283-1299.
APA	Barmpalias, G,Fang, N,&Lewis-Pye, A.(2016).Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega.JOURNAL OF COMPUTER AND SYSTEM SCIENCES,82(8),1283-1299.
MLA	Barmpalias, G,et al."Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega".JOURNAL OF COMPUTER AND SYSTEM SCIENCES 82.8(2016):1283-1299.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
Optimal asymptotic b（571KB）			开放获取	使用许可	请求全文