2
$\begingroup$

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

2 Answers 2

2

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$.)

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.

  • 0
    $A$ is $\omega$-c.e. if there exists a computable function $f : \omega \times \omega \rightarrow \{0,1\}$ and a computable function $g: \omega \rightarrow \omega$ such that $\lim_{s \rightarrow \infty}f(x) = A(x)$ and for all $x$, $|\{s : f(x,s) \neq f(x, s + 1)\}| \leq g(x)$. Intuitively, there is a computable approximation $f$ to $A$ where the number of times the approximation changes is bounded by $g(x)$. For example $c.e.$ sets have an approximation that may change only once, i.e. something is enumerated in but once in can never be taken out.2012-05-17