Turing reducible in natural numbers?

Question

I'm confused about Turing reducible things.

I understanded Turing reducible like this

"There is an oracle algorithm which is about set A and when this algorithm is derived from oracle algorithm of set B, it is called A is Turing-reducible to B"

So by this, I have to solve the problem.

N is the set of natural numbers = {1, 2, 3, ...}

Let A be the set of all even natural numbers.

Let B be the set of all odd natural numbers.

Prove that A is Turing-reducible to B.

Here is what I have thought.

The oracle algorithm of A is n%2==0 which n belongs to natural numbers.

And oracle algorithm of B is n%2==1 which n belongs to natural numbers.

How can I derive n%2==0 from n%2==1 ?

Or my approach is wrong?

Thanks for your help.

Answer 1

To show that $A$ is Turing-reducible to $B$ you need to prove the existence of a Turing Machine that is able to decide $A$ when given access to an oracle for $B$.

In your specific case a possible Turing Machine $M$ takes as input a string $x \in \{0,1\}^*$ encoding the natural number $n$ (I'm assuming $0 \in \mathbb{N}$) in binary and operates as follows:

• It flips the last bit of $x$. Now $x$ represents an odd number iff the input number $n$ was even.
• It invokes the oracle for $B$ with input $x$.
• It accepts iff, according to the oracle, $x \in B$.

Notice that the fact that $M$ has access to an oracle for $B$ does not mean that $M$ must use that oracle. The following is also a valid choice for $M$:

• Locate the last bit $y$ of the input string $x$.
• If $y=0$ accept. Otherwise reject.