What does it mean to be Turing reducible?

Question

I'm confused about what it means to be Turing reducible. I thought I understood what it meant, but apparently not.

$A \leq B $ Means that A is Turing reducible to B. This means that given an oracle for Machine B, A can be solved.

I'm confused in the case of SUPERHALT which decides whether a Turing machine with access to the HALT oracle halts or not. I feel like SUPERHALT is reducible to HALT because I can just put any Turing machine into a HALT oracle and then put that result into another HALT oracle.

So in summary I believe:

Given a Turing machine M and input x $\epsilon \{1,0\}^*$ and oracle $HALT$, $$SUPERHALT(M(x)) <_T HALT(M(x))$$ because $$SUPERHALT(M(x)) = HALT(HALT(<M(x)>)$$ Which is wrong, but I just want to know what I'm misunderstanding.

Answer 1

From wikipedia article Turing Reduction, in computability theory, a Turing reduction from a problem $A$ to a problem $B$, is a reduction which solves $A$, assuming the solution to $B$ is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve $A$ if it had available to it a subroutine for solving $B$. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for $B$. Turing reductions can be applied to both decision problems and function problems.

This potentially allows us, along with a few other things, to solve problem $A$ using a deterministic Turing machine if $B$ is solvable using deterministic Turing machine.

I assume $SUPERHALT = \{ \langle M,x \rangle \ | \ M^{HALT}$ halts on input $x \}$. If so, then your reduction is incorrect.

First of all, a Turing machine $M$, that uses $HALT$ as an oracle, cannot be used as a non-oracle machine and given as an input of $HALT$. So using something like $HALT(\langle M, x \rangle)$ leads nowhere.

We can use relativizing proof to prove that $SUPERHALT$ is unsolvable even with availability of $HALT$ as an oracle. We simply take Turing's original proof (with the machine given as self-input) that the halting problem is unsolvable, and give all the machines an oracle for the halting problem. Everything in the proof goes through as before.

From the fact that $SUPERHALT$ is unsolvable (even with the availability of $HALT$ as an oracle) we can prove $SUPERHALT \not\leq_T HALT$. Suppose there is a turing reduction $M'$ for $SUPERHALT$, which uses $HALT$ as a subroutine. Then this $M'$ which uses $HALT$ as an oracle is able to decide $\langle M^{HALT},x\rangle \in SUPERHALT$. This is a contradiction. Hence $SUPERHALT \not\leq_T HALT$.

Answer 2

$A\leq B$ means that $A$ is Turing reducible to $B$. This means that given an oracle for Machine $B$, $A$ can be solved.

This is very close to correct, yes. Being picky, $A$ and $B$ here are languages, not machines, but that's not super-important. The key intuition here is that, if $A\leq B$ then, if you were given a subroutine for $B$ (which is, essentially, what an oracle is), you could solve $A$. This measn that, in a sense, $A$ is no harder than $B$.

Your intuition that what you're calling $\text{SUPERHALT}$ reduces to the ordinary halting problem, however, is incorrect. It's very easy to write down things like "$\text{SUPERHALT}(M(x)) = \text{HALT}(\text{HALT}(M(x)))$" but I'm not sure that statement actually means anything. For example, the argument of $\text{SUPERHALT}$ is a Turing machine with an oracle for the halting problem. So it doesn't make sense to write $\text{HALT}(M(x))$ because the argument to $\text{HALT}$ is supposed to be an ordinary Turing machine, not an oracle machine. So, when you write an equation, stop and check that it actually makes sense.

In fact, it can be shown that $\text{SUPERHALT}\not\leq\text{HALT}$. The proof of this uses essentially the same diagonalization as the proof that $\text{HALT}$ is not decidable. Intuitively, we expect $\text{SUPERHALT}$ to be strictly harder than $\text{HALT}$ because $\text{SUPERHALT}$ asks the halting question about more powerful machines (oracle machines) than $\text{HALT}$ does (ordinary machines).