# Proving undecidability of the language composed of LBAs where their language is empty

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?

• 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'$?
– Raphael
Apr 2 '13 at 7:44

## 1 Answer

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.