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

作者：

Highlights：

• 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.

摘要

•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.

论文关键词：Halting probability,Oracle use,Oracles,Optimal,Asymptotic,Kolmogorov,Completeness,Computability,Complexity

论文评审过程：Received 5 February 2016, Revised 3 May 2016, Accepted 5 May 2016, Available online 11 June 2016, Version of Record 15 July 2016.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.05.004