# Turing reducible in natural numbers?

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?

• What does it mean to "orient" an algorithm? To provide a Turing reduction from A to B you need to show Turing Machine that has access to an oracle for B and is able to solve A. – Steven Apr 12 at 10:02
• @Steven I meant "derive". Sorry for confusing. – Sungtaek Yang Apr 12 at 10:16

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.