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

protected by Community Oct 22 '18 at 9:48

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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