0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ Commented Sep 20, 2016 at 23:16
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ Commented Sep 20, 2016 at 23:17
  • $\begingroup$ Hint: Constructing Turing-reductions, you can use the "inner machine" in any way you want. You can manipulate input(s) and output(s), and call it multiple times. $\endgroup$ Commented Sep 20, 2016 at 23:19

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.