4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 27 '17 at 13:31
  • $\begingroup$ @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)? $\endgroup$ – Jazz Feb 27 '17 at 13:34
  • $\begingroup$ No, the reduction there seems to be in the stated direction. $\endgroup$ – Yuval Filmus Feb 27 '17 at 13:37
  • $\begingroup$ @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 ):. $\endgroup$ – Jazz Feb 27 '17 at 13:44
  • $\begingroup$ Try matching what you did to the definition you have. You don't need us for that. $\endgroup$ – Yuval Filmus Feb 27 '17 at 13:45
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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