Consider an operator $+$ defined on $P(N)$ as follows: $A + B = \{2x\mid x \in A\}\cup \{2x + 1\mid x \in B\}$

Show that both $A$ and $B$ are Turing-reducible to $A+B$

I am kind of confused about this notion of turing reducibility thing.
Does it mean that There is a turing machine which converts an input from $A$ to an element of $B$
on the tape. There is a term called oracle that also pops up. So if we have an oracle for $B$
does it mean that there is a decider for $B$? What's an intuitive workable definition of oracle?


The definition of Turing reducible, is that there exists a Turing reduction - an algorithm for $A+B$ that uses an oracle to $A$.

To understand this, you must first understand oracle machines. Those machines, are like turing machines, but can ask an "oracle" whether any $x$ is in $A$ or not, and would get an answer in $O(1)$, regardless of what $A$ is (doesn't even matter if it is not decidable!)

So, a turing reduction basically means that if you know for any $x$ whether its in $A$ or not in $A$, then you can decide whether a given $x$ is in $A+B$. Formally, this statement can be written as ${(A+B)}^A\in R$.

So basically the question asks you to show that ${(A+B)}^A,{(A+B)}^B\in R$

  • $\begingroup$ So when asked to show that A is turing reducible to A+B. Does that amount to that if given y we could determine if it is in A+B. by using the oracle for A ? So if y/2 is in A then y is in A+B certainly. But in case y is of the form 2x+1 where x is in B. In that case we don't have an oracle for B to determine this. I am kind of confused here how to complete the argument $\endgroup$ Mar 31 at 10:54
  • $\begingroup$ If I understand correctly there is no need to run a turing machine with states and symbols here. And when you talk about oracle for A it just means there is a decider for A $\endgroup$ Mar 31 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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