If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ What if $B = \emptyset$? $\endgroup$– Yuval FilmusCommented Oct 20, 2020 at 23:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
That is false. Consider for example the alphabet $\Sigma = \{0,1\}$ and the two languages $A = \emptyset$ and $B = \Sigma^*$.
Clearly both $A$ and $B$ are decidable (by the trivial algorithms that always reject and always acccept, respectively) but it is false that $A \le_m B$.
