Computing the halting problem with no computable bound on the use function

Question

I would like to prove that there are two sets $A,B\subset \mathbb{N}$ such that

• $A |_T B$
• $\emptyset' \equiv_T A\oplus B$
• for every $e$, if $\{e\}^{A\oplus B}=\emptyset'$ then the map sending $(B,n)$ to the prefix of $B$ used in the computation $\{e\}^{A\oplus B}(n)$ is not computable.

I believe the existence of $A,B$ as above can be proved with a not-so-hard (but maybe not entirely trivial) finite extension argument. However, since these arguments are often tedious to read, and even more to write, I was wondering whether the existence of $A,B$ follows more easily by some result in classical computability.

Answer 1

The answer is yes.

Since Chaitin's $\Omega$ is $wtt$-reducible to $\emptyset'$, we may replace $\emptyset'$ with $\Omega$.

Now let $A<_T \emptyset'$ be a $K$-trivial but promptly simple set. Then there is an incomplete c.e. set $B$ so that $\emptyset'\equiv_T A \oplus B$.

Suppose that there is such an $e$. Since $B$ is c.e. but incomplete, it must be non-$DNC$. So there is a partial computable function $g$ so that

$ \exists^{\infty}n(g(n)\mbox{ is the prefix as required})$.

(Note that $B$ can be low and so non-high. Then we may assume that $g$ is totally computable.)

Therefore for any such $n$, $K(\Omega \upharpoonright n)\leq K(A\upharpoonright |g(n)|)+K(g(n))\leq 2K(n)$ up to a constant. This is a contradiction.