Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers

详细信息    查看全文

• 作者：George Barmpalias^a ; ^b ; ^{barmpalias@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Andrew Lewis-Pye^c ; ^{A.Lewis7@lse.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Jason Teutsch^d ; ^{teutsch@uab.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Kučera&ndash ; G&aacute ; cs theorem ; Computation from random oracles ; Optimal redundancy bounds ; Betting strategies ; Martingales
• 刊名：Information and Computation
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：251
• 期：Complete
• 页码：287-300
• 全文大小：480 K

文摘

The Kučera–G&aacute;cs theorem is a landmark result in algorithmic randomness asserting that every real is computable from a Martin-Löf random real. If the computation of the first n   bits of a sequence requires ace0f13427403f69e47dfd7c9d04b8" title="Click to view the MathML source">n+h(n)$n+h(n)$ bits of the random oracle, then h is the redundancy   of the computation. Kučera implicitly achieved redundancy nlog⁡n$n\log n$ while G&aacute;cs used a more elaborate coding procedure which achieves redundancy $\sqrt{n}\log n$. A similar bound is implicit in the later proof by Merkle and Mihailović. In this paper we obtain optimal strict lower bounds on the redundancy in computations from Martin-Löf random oracles. We show that any nondecreasing computable function g   such that ∑_n2^−g(n)=∞${\sum }_n{2}^{-g(n)}=\infty$ is not a general upper bound on the redundancy in computations from Martin-Löf random oracles. In fact, there exists a real X such that the redundancy g of any computation of X   from a Martin-Löf random oracle satisfies ∑_n2^−g(n)<∞${\sum }_n{2}^{-g(n)}<\infty$. Moreover, the class of such reals is comeager and includes a ${\mathrm{\Delta }}_2^0$ real as well as all weakly 2-generic reals. On the other hand, it has been recently shown that any real is computable from a Martin-Löf random oracle with redundancy g, provided that g   is a computable nondecreasing function such that ∑_n2^−g(n)<∞${\sum }_n{2}^{-g(n)}<\infty$. Hence our lower bound is optimal, and excludes many slow growing functions such as ac69da363c521b1cb7e9280" title="Click to view the MathML source">log⁡n$\log n$ from bounding the redundancy in computations from random oracles for a large class of reals. Our results are obtained as an application of a theory of effective betting strategies with restricted wagers which we develop.