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 $xin L_1 Leftrightarrow f(x)in L_2$. The function $f$ just works as follows. Given a word $ain 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 $ain L_2$ and a word $bnotin 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
