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?
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.
-
$\begingroup$ Yes, this adds a bit more clarity to reducibility - thank-you! $\endgroup$ – user2896468 Nov 4 '14 at 9:16