Reduction from undecidability, decidability to decididabilty

Question

If given any two language both $L_1$ and $L_2$ are decidable then why both $L_1\leq_m^\mathsf{}L_2$ and $L_2\leq_m^\mathsf{}L_1$ are false. Please provide easy explanation with any counterexample for both cases.

Any language $L_3$ is given as Undecidable and $L_4$ is decidable then $L_3\leq_m^\mathsf{}L_4$ is false. But $L_4\leq_m^\mathsf{}L_3$ is true. What's the reason behind it?

I can't differentiate between above two concepts. Please explain with example.

Answer 1

If $L_1$ is decidable and $L_2$ is decidable then it is not necessarily true that $L_1 \le_m L_2$. Consider for example any $L_1$ distinct from $\emptyset$ and pick $L_2 = \emptyset$.

In general, if $A$ and $B$ are languages, $A$ is decidable, and $B$ is non-trivial (i.e., distinct from $\emptyset$ and $\Sigma^*$) then $A \le_m B$ holds. The actual reduction is easy:

• Let $y \in B$ and $n \not\in B$ be some fixed words. Their existence is guaranteed by the fact that $B$ is non-trivial.
• Given a word $x$, check whether $x \in A$. This can be done since $A$ is decidable by hypothesis.
• If $x \in A$ return $y$. Otherwise return $n$.

This shows that for any pair of non-trivial decidable languages $L_1, L_2$ you have both $L_1 \le_m L_2$ (by picking $A=L_1$ and $B=L_2$) and $L_2 \le_m L_1$ (by picking $A=L_2$ and $B=L_1$).

Let's now consider whether $L_3 \le_m L_4$ holds when $L_3$ is undecidable and $L_4$ is decidable. This is false since it would imply that $L_3$ is decidable. Indeed, if we suppose towards a contradiction that $L_3 \le_m L_4$, we have that the following algorithm decides $L_3$:

• Let $f$ be any fixed many-one reduction from $L_3$ to $L_4$. Notice that $f$ exists by hypothesis.
• Given a word $x$, compute $z=f(x)$. This can be done because $f$ is a total computable function by definition of many-one reduction.
• Check whether $z \in L_4$. This can be done since $L_4$ is decidable.
• If $z \in L_4$ return "yes". Otherwise return "no".

Finally, let's consider $L_4 \le_m L_3$. This is true since $L_3$ is necessarily non-trivial because it is undecidable (and all trivial languages are decidable by either the algorithm that always returns "yes" or by the algorithm that always returns "no"). Then we can use the reduction discussed above by picking $A=L_4$ and $B=L_3$.