As it is explained in Sipser's book, the following language is undecidable and he proves this using the computation history method.

$\qquad E = \{\langle M \rangle \mid M\ \mathrm{LBA}, L(M)=\emptyset\}$

I wanted to see if we could use the same method used for proving undecidability of the following language in the case of LBAs too (instead of using computation history method).

$\qquad E' = \{\langle M \rangle \mid M\ \mathrm{TM}, L(M)=\emptyset\}$

Is it possible?

  • $\begingroup$ You have been asking many similar questions in short succession. What have you tried? Also, I don't quite get what you are asking. Are you looking for a new undecidability proof for $E$ or $E'$? $\endgroup$
    – Raphael
    Apr 2 '13 at 7:44

Consider the reduction that shows that LBA-emptiness is undecidable: you reduce from $\overline{A_{TM}}=\{<M,w>: M $ does not accept $w\}$.

So the reduction takes as input $<M,w>$, and outputs an LBA $T$ such that $L(T)\neq \emptyset$ iff $M$ accepts $w$.

Now, recall that an LBA is in particular a TM. So this same reduction actually outputs a TM, and actually shows that $E_{TM}$ is undecidable as well.

The reason this works is that the relationship between $E_{LBA}$ and $E_{TM}$ is such that if $M$ is an LBA, then $M\in E_{LBA}$ iff $M\in E_{TM}$. Since the reduction above always outputs an LBA, then you can just plug it in.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.