1
$\begingroup$

Question: Prove the following: Every set is Turing reducible to itself.

If anyone can provide a solution that would be great, I've just been introduced to computation theory so be as descriptive as you like for my sake if not strictly for the answer. Thanks!

$\endgroup$
3
$\begingroup$

Informally, $A$ is Turing reducible to $B$ if you can figure out what $A$ is by asking questions to $B$.

A bit more formally, $A$ is Turing reducible to $B$ if there's some algorithm you can use to figure out whether a number is in $A$ by asking questions about whether or not various numbers are in $B$. For example, an instance of a Turing reduction between $A$ and $B$ might look like the following:

  • I want to figure out whether $3$ is in $A$.

  • I ask $B$, "Is $17$ in you?"

  • $B$ says yes.

  • I now say, "Okay, based on that answer I now want to ask: is $42$ in you?"

  • $B$ says no.

  • I say, "Great! Now I know that $3$ is in $A$.

So, you're trying to do the following: given some arbitrary set $A$ and an arbitrary number $n$, find a way to figure out whether $n$ is in $A$ by "querying" $A$. (HINT: don't overthink this ...)


Incidentally, Turing reductions don't have to be efficient, or non-stupid, or anything else nice; they just have to work. For example, in the problem you're trying to solve, there is a "best" Turing reduction; but we could also modify that reduction to pointlessly ask "Is $17$ in $A$?" at the end for absolutely no reason, and simply ignore that extra information.

$\endgroup$
  • $\begingroup$ "Turing reductions don't have to be non-stupid" -- wise words, indeed! $\endgroup$ – chi Oct 22 '18 at 14:23

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