Turing reduction

Question

I'm learning algorithm theory. Homework question is:

Are $A$ and $B$ possible so that $A\not\le_{tt}B$ (impossible to reduce using tt), but $A\le_T B$.

But I can't think of any example..

Answer 1

Since this is a homework, I'll only give a hint. This hint follows Rogers' Theory of Recursive Functions and Effective Computability, chapter 9, page 127.

Let $\langle g_{i}\rangle_{i \in \mathbb{N}}$ be an effective listing of all the Boolean functions, with $a_i$ the arity of $g_i$. Then $A \leq_{tt} B$ iff there is a computable function $f$ so that $A(n) \Leftrightarrow g_{f(n)}(B\upharpoonright a_{f(n)})$. Let $K$ be the halting set and define $\tilde{K} = \{e| \exists i [\varphi_{e}(e)\downarrow = i \; \& \; g_{i}(K\upharpoonright a_{i})\}$. Show that $\tilde{K} \nleq_{tt} K$ but $\tilde{K} \leq_{T} K$. (Another hint: use the fact that $A \leq_{tt} B$ iff $A^{\complement} \leq_{tt} B$.)

Answer 2

I think the most elucidating method of solving this problem is to construct such set; however, if you are willing to accept some facts you can get a very quick solution.

Lemma: The following are equivalent

1. $A$ is $\omega$-c.e.

2. $A \leq_{tt} \emptyset'$

3. $A \leq_{wtt} \emptyset'$

You don't really need the 3 but it is interesting that the two reductions are equivalent below $\emptyset'$. This is proposition 1.4.4 on page 19 of $\textit{Computability and Randomness}$ by Andre Nies.

Now if you believe if there limit computable ($\Delta_2^0$) i.e. $\leq_T \emptyset'$ which is not $\omega$-c.e., the result follows. One way of proving that there exists a $\Delta_2^0$ not $\omega$-c.e. set is by a finite injury argument.