# In which direction should I carry out a reduction when proving decidability/recognizability?

Definition:

$\text{A fuction}\ f: \Sigma^* \to \Sigma^*\ \text{is a reduction from Language A to language B if}\ w\in A \iff f(w) \in B\ \text{for every}\ w \in \Sigma^*$.

My question is which direction should I take in order to reduce a problem to another the other?

From what I've been reading I concluded we can prove that $A \leq_m B$ is we can use the TM of $B$ in order define the operation of the TM of $A$.

Let suppose I want to show that any co-recognizable language $L_k$ reduces to $\overline{HALT} = \{(\langle M \rangle, w): M(w)\ \text{doesn't halt}\}$, that is $L_k \leq_m \overline{HALT}$.

Then if $T$ is the machine working on $w \in L_k$ then I think we can make it work in this way

T on input w
Run M on w;
If M(w) = Halt
Then Halt;
Else
Loop;


So if $w \notin \overline{HALT}$, then $M(w)$ halts and $T(w)$ halts $\implies w\notin L_k$.

If $w \in \overline{HALT}$, then $M(w)$ doesn't halt and $T(w)$ doesn't halt $\implies w\in L_k$.

Now suppose I want to prove that any co-recognizable language $L_k$ reduces to $L_{all} = \{\langle N \rangle: N\ \text{halts on every input}\}$.

My idea was to show that $\overline{HALT} \leq_m L_{all}$ and then by transitivity follows that $L_k \leq_m L_{all}$.

So I have to ''use'' the machine $R$ operating on $L_{all}$ to define a machine $P$ operating on $\overline{HALT}$.

Bu then I found this post Is the language of Turing Machines that halt on every input recognizable? which confused me a bit. There is shown that, indeed, $\overline{HALT} \leq_m L_{all}$ $(\overline{H} \leq_m AH$ in the notation of the cited post), but using the machine operating on $\overline{HALT}$ (with its corresponding input) to define the machine operating on $L_{all}$. To my eyes, it looks like the other way around.

So I'm lost.

One thing that gives peace to my soul is that all $m$-complete language are isomorphic. So probably I could shield myself behind this, assume that $L_{all}$ is $m$-complete in the class of co-recognizable language just as $\overline{HALT}$, and show what was shown in the post above. I mean, loosely speaking, assume the direction of reduction doesn't matter.

But if I don't want make this assuptiom (that $L_{all}$ is m-complete and therefore isomorphic) and just show that $\overline{HALT} \leq_m L_{all}$. Is valid to go from $(\langle P\rangle, w) \to R$

• The answer is given by your definition. The wording is somewhat ambiguous, apparently some people meaning different things by the same phrase, but in your case you have a definition, and this disambiguates the phrase. – Yuval Filmus Feb 27 '17 at 13:31
• @YuvalFilmus Does it mean that in the question of the other post/thread what was shown was actually $AH \leq_m \overline{H}$ ($L_{all} \leq_m \overline{HALT}$in my notation)? – Jazz Feb 27 '17 at 13:34
• No, the reduction there seems to be in the stated direction. – Yuval Filmus Feb 27 '17 at 13:37
• @YuvalFilmus Mmm. Then I was the one who carried out the reduction $L_k \leq_m \overline{HALT}$ above in the other way around? Sorry, I'm not getting it ):. – Jazz Feb 27 '17 at 13:44
• Try matching what you did to the definition you have. You don't need us for that. – Yuval Filmus Feb 27 '17 at 13:45

## 1 Answer

When we reduce a language A to a language B, we take an instance $x$ of A and transform it into an instance $f(x)$ of B so that $x \in A$ iff $f(x) \in B$. The way to remember that this is the correct direction is that shows you how to decide A if you can decide B. This is the normal, everyday life meaning of "reduction".

The linked answer does exactly that – it transforms an instance of $\overline{HALT}$ to an instance of $L_{all}$, thus reducing $\overline{HALT}$ to $L_{all}$.