# How to prove the following: Every set is Turing reducible to itself

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!

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.

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