# Is Turing Reduction always in context to decidable languages?

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 ?

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.

• Sorry..my question didn't expressed the thought clearly. I've updated the question – Laschet Jain Aug 25 '16 at 21:39
• @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. – jmite Aug 25 '16 at 21:44
• But as dino wrote oracle must halt on every input, right? and can't that just happen when B is assumed to be decidable? – Laschet Jain Aug 25 '16 at 21:49
• @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. – jmite Aug 26 '16 at 15:41

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

• Don't we assume it to be decidable (for that moment) by claiming that if we could solve B? – Laschet Jain Aug 25 '16 at 21:34
• @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." – David Richerby Aug 25 '16 at 22:08

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.

• 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. – David Richerby Aug 25 '16 at 23:08
• @DavidRicherby Yes, using a Gödel numbering one can view those as natural numbers. I will add it to my answer. – Dino Rossegger Aug 26 '16 at 8:14