Cheap and Secure Web Hosting Provider : See Now

[Solved]: Proving undecidability of the language composed of LBAs where their language is empty

, , No Comments
Problem Detail: 

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?

Asked By : msn

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10934

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback