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?
3
$\begingroup$
$\endgroup$
5
$\begingroup$
$\endgroup$
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
