Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

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

share|improve this answer

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.

share|improve this answer
    
What is the definition of $\omega$-c.e.? –  Quinn Culver May 17 '12 at 17:44
    
$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. –  William May 17 '12 at 19:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.