0
$\begingroup$

According to Wikipedia's article on Turing Reduction

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.

Does solving mean always halting (accept/reject)? Should B assumed to be decidable language for the sake of proofs ?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

Absolutely not. In fact, these are most useful when $B$ is undecidable.

Diagonalization was used to show the Halting problem undecidable, but most other problems were shown to be undecidable through a reduction:

  1. Suppose we have a subroutine solving $B$
  2. Show that we can use that subroutine to solve $A$.
  3. If $A$ is undecidable, then we have a contradiction, so we know $B$ must also be undecidable.

That said, the a proper Turing reduction should always halt. It's cheating if you say "I can use $B$ to make a program that either solves $A$ or runs forever". That's not useful in general.

(Although if you used $B$ to find a recognizer for $A$ where $A$ is not recursively-enumerable, you could show that $B$ is not decidable/recursively-enumerable, depending on your initial assumption about $B$.)

If $B$ is decidable, and you reduce $A$ to $B$, all you've done is create an algorithm deciding $A$. Which is useful, but you don't need a formal notion of reduction to do that.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Sorry..my question didn't expressed the thought clearly. I've updated the question $\endgroup$
    – Laschet Jain
    Aug 25, 2016 at 21:39
  • $\begingroup$ @LashitJain: my answer still covers this. A proper Turing reduction , B is assumed to halt, as is the reduction. But you can still prove interesting things if you don't assume $B$ halts, or if you don't assume your reduction halts. $\endgroup$
    – jmite
    Aug 25, 2016 at 21:44
  • $\begingroup$ But as dino wrote oracle must halt on every input, right? and can't that just happen when B is assumed to be decidable? $\endgroup$
    – Laschet Jain
    Aug 25, 2016 at 21:49
  • $\begingroup$ @LashitJain The answer is unchanged. To fit the proper definition of a Turing reduction, $B$ must halt. But you can still use a non-halting $B$ to prove interesting things, like a problem not being recursively enumerable. $\endgroup$
    – jmite
    Aug 26, 2016 at 15:41
2
$\begingroup$

The first point to make is that "solving" here is not a formal term, so it doesn't have a fixed definition. It means – and please forgive the circularity, here – solving the problem in whatever sense we're talking about at the moment. That could be deciding it, semi-deciding it or something else.

With that out of the way, the answer to your main question is "no". It is not necessary for $B$ to be decidable if we want to reduce a language to it. All that we're saying is if we could solve $B$, then we could use that to solve $A$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Don't we assume it to be decidable (for that moment) by claiming that if we could solve B? $\endgroup$
    – Laschet Jain
    Aug 25, 2016 at 21:34
  • $\begingroup$ @LashitJain No, not at all. No more than I assume that you have superpowers when I say "If you had superpowers, you could leap tall buildings in a single bound." $\endgroup$
    – David Richerby
    Aug 25, 2016 at 22:08
2
$\begingroup$

Yes, $A$ is Turing reducible to $B$ if there is an algorithm that, having a subroutine for solving $B$, halts on any input.

In computability theory we like to think about such algorithms as Oracle Turing Machines. Using a Gödel numbering we can view strings of languages as natural numbers. Therefore we view languages $A, B$ as sets of natural numbers, where $x \in A$ if the string having Gödel number x is in the language. An oracle Turing machine is then a Turing machine with an additional tape, and an additional command that tests whether a number $x$ is on the oracle tape.

A set $A$ is then Turing reducible to $B$, $A\leq_T B$, if there is an oracle Turing machine $\phi$ such that $$\phi^B= \chi_A$$ ($\phi^B$ is $\phi$ initialized with $B$ on the oracle tape) where $\chi_A$ is the characteristic function of $A$, i.e., $\chi_A(x)=1$ if $x\in A$ and $\chi_A(x)=0$ otherwise. As $\chi_A$ is total, $\phi^B$ must halt on every input.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Note that, in a computer science context, languages are usually sets of strings over some finite alphabet, rather than sets of natural numbers, though this doesn't make any real difference. $\endgroup$
    – David Richerby
    Aug 25, 2016 at 23:08
  • $\begingroup$ @DavidRicherby Yes, using a Gödel numbering one can view those as natural numbers. I will add it to my answer. $\endgroup$
    – Dino Rossegger
    Aug 26, 2016 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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