[Solved]: What does it mean to be Turing reducible?

Problem Detail: 

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.

Asked By : user3743825

Answered By : Shreesh

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54576

 Ask a Question

 Download Related Notes/Documents