[Solved]: Could two decidable languages ever not have a mapping reduction?

Problem Detail: 

Is it ever the case that two decidable languages $L_1$ and $L_2$ that cannot be reduced to one another (in either or both directions)? Intuitively, I would not expect there to be, but rigorously, are there extreme examples that prove otherwise?

Asked By : user2896468

Answered By : Hoopje

If you are talking about reduction in general (not polynomial reduction), then you basically can put all the logic in the reduction function. Suppose $L_1$ and $L_2$ are decidable languages. To reduce $L_1$ to $L_2$ we need a computable function $f$ such that $x\in L_1 \Leftrightarrow f(x)\in L_2$. The function $f$ just works as follows. Given a word $a\in L_2$ and a word $b \notin L_2$:

$f(x) = \begin{cases} a & \text{if } x \in L_1 \\ b & \text{if } x \notin L_1 \end{cases}$

This function is computable because $L_1$ is decidable by assumption.

However, the above also points you to the exceptions. It assumes that there is a word $a\in L_2$ and a word $b\notin L_2$, and there exactly two languages for which this is not the case. Both of those languages are decidable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32668