Assume that a language A is reducible to language B. The claim is true?
if A is decidable then B is decidable too.
The correct answer is:
This claim is wrong. If A is e.g. the empty language (which is clearly decidable) and B is $A_{TM}$, then surely ∅ is reducible to $A_{TM}$, but $A_{TM}$ is undecidable. The claim is true the other way round: If B is decidable then A is decidable too.
I have problem to understand two points:
- A is e.g. the empty language (which is clearly decidable)
Why empty language is ("clearly") decidable and $L_∅$ is not?, where, $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$
- **A is reducible to $A_{TM}$ **
I have difficulties to image a reduction from $∅$ to $A_{TM}$, where $A_{TM} = \{<M,w> | \ M \ is \ a \ TM \ and \ M \ accepts \ w\}$