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

Question

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$

Answer 1

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