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

The paper deals with oracle computations of infinite binary sequences with an infinite binary sequence as oracle. It considers binary expansions of computably enumerable reals \(\alpha\), that is, reals which are computably approximable from below, and characteristic sequences \(A\) of computably enumerable subsets of \(N\). For a function \(h: N\to N\), a sequence \(A\) is said to be computable from a sequence \(B\) with use bounded by \(h\) if there exists an oracle Turing machine which, for any \(n\), given the first \(h(n)\) bits of \(B\) on the oracle tape, outputs the first \(n\) bits of \(A\). Let \(h\) be a computable function such that \(h(n) - n\) is non-decreasing. Then the following conditions are equivalent. 1. \(\sum_{n=0}^\infty 2^{n-h(n)}<\infty\) 2. for every computably enumerable real \(\alpha\) there exists a Turing machine which computes \(\alpha\) from Chaitin's \(\Omega\) with use bounded by \(h\). A similar characterisation with respect to computations of characteristic sequences of computably enumerable subsets of \(N\) from \(\Omega\) is also obtained. Here the following holds. Let \(g\) be a computable non-decreasing function \(g:N\to N\). Then \(\sum_{n=0}^\infty 2^{-g(n)}< \infty\) if and only if for every characteristic sequence \(A\) of a computably enumerable subset of \(N\) the sequence \(\Omega\) computes \(A\) with use bounded by \(g\). Further results and some connections with Solovay functions are given.