Turing reducible in natural numbers?
-
29-09-2020 - |
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.
Solution
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.