1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Steven Apr 12 at 10:02
  • $\begingroup$ @Steven I meant "derive". Sorry for confusing. $\endgroup$ – Sungtaek Yang Apr 12 at 10:16
2
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$

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.