reduction from the problem "accepts-empty string" to "language of empty string"

Question

9.9. Construct a reduction from Accepts-$\lambda$ to the problem Accepts-$\{\lambda\}$: Given a TM $T$ , is $L(T) = \{\lambda\}$?

The question is from Martin's Introduction to Languages and Theory of Computation.

I know how reductions work though I am unsure of several things. It's easy to see that if the inner machine (computing "accepts-$\{\lambda\}$") accepts then the outer must also accept, but it is not clear that the other goes as well. How do I ensure this?

Answer 1

Call $L_1=\{\langle M \rangle\mid M\text{ accepts }\lambda\}$ and $L_2=\{\langle M \rangle\mid M\text{ accepts only }\lambda\}$, where $\langle M\rangle$ denotes the description of the TM $M$. We wish to establish a mapping reduction $L_1 \le_\text{M} L_2$.

To do this, we want a mapping, $f$, from TM descriptions to TM descriptions such that $$ \langle M\rangle\in L_1 \Longleftrightarrow f(\langle M\rangle)\in L_2 $$ For a TM description $\langle M\rangle$, we'll define $f(\langle M\rangle)=\langle N\rangle$ where

N(x) =
   if x = lambda
      run M on input lambda
      if M accepts
         accept

Now what happens with this mapping?

• If $M(\lambda)$ accepts (so $\langle m\rangle\in L_1)$, $N$ will accept $\lambda$ and no other string, so $\langle N\rangle\in L_2$.
• If $M(\lambda)$ doesn't accept (so $\langle M\rangle\notin L_1)$, $N$ will accept no input string, so $L(N)=\varnothing$ and thus $\langle N\rangle\notin L_2$.

That's exactly what we need to establish the reduction $L_1 \le_\text{M} L_2$.