Turing reduction

I'm finding out algorithm concept. Research inquiry is:

Are $A$ and also $B$ feasible to make sure that $A\not\le_{tt}B$ (difficult to lower making use of tt), yet $A\le_T B$.

Yet I can not consider any kind of instance.

2022-07-25 17:47:10
Source Share
Answers: 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 , 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$.)

2022-07-25 19:24:27