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.
