Question

Show that for any language A , a language B exists,where$\mathit{A}{\mathbf{\le }}_{\mathbf{T}}\mathbf{}\mathbf{}\mathit{a}\mathit{n}\mathit{d}\mathbf{}\mathit{B}{\mathbf{\text{'}}}_{\mathbf{T}}\mathit{A}\mathbf{.}$ .

Short answer

Answer:

There exist a language B for language A , where A${\le }_T$B and B'${}_{T}A$ .

Step-by-step solution

Turing Reducible

In theory of computation, if a language $L_{1_{}}$is decided by a Turing Machine based on another language $L_{2_{}}$, then we say that A can be decidable to $L_{2_{}}$, or $L_{1_{}}$is Turing Reducible to $L_{2_{}}$. It is denoted as $L_1{\le }_T{L}_2$.

Proving

In this question, we need to prove that, “A is Turing Reducible to B but B but is not Turing Reducible to A”.

Let $A=E_{T{M}_{}}=Emty$Turing Machine ={<M>| M is a Turing Machine and language L$\left(M\right)=\varphi \}$

And B = $A_{T{M}_{}}$= Oracle Turing Machine Machine ={<,w>| Machine M accept string w}

Let us first prove $A{\le }_{T}B$

To prove it, we need to prove $E_{TM}{\le }_T{A}_{TM}$

We know that $E_{TM}$is decidable relative to $A_{TM}$.

Since, above is true, that means A is decidable relative to B then A ${\le }_T$B.

Now we will prove that B' ${}_{T}A$

To prove this, we need to prove $A_{TM}{\text{'}}_T{E}_{TM.}$.

Let us assume that $A_{TM}\text{'}{}_T{E}_{TM.}$.

Now by mapping reducibility rules for any two language : language $x\le my<x{\le }_{m}y:Languagex$is map reducible to language y .

If there is a computable function f : $\in *\to \in *$

Here, for every w, function f called reduction of x to y .

This means, w e x, f(w) e y

From above reduce mapping, we can conclude that $A_{TM}{\le }_T{E}_{TM},A_{TM}{\le }_M{E}_{TM}$

But, $E_{TM}$is Turning Recognizable but $A_{TM}$ is not.

This violates mapping reducibility as both must be Turing Recognizable.

So, our assumption was wrong that .$A_{TM}{\le }_T{E}_{TM}$

Hence, B'${}_{T}A$

Therefore, we conclude that: and $A{\le }_{T}B$and $B\text{'}{}_{T}A.$'.