2
$\begingroup$

How is the emptiness of Linear Bound Automata (LBA) i.e $L = \{B \mid L(B) = \emptyset \}$ is undecidable?

$\endgroup$
1
  • $\begingroup$ Thanks for the edit. $\endgroup$ – SiluPanda Apr 20 '19 at 15:38
1
$\begingroup$

Given a Turing machine $M$, we can construct an LBA $B$ which on input of length $n$ checks whether $M$ halts on the empty input within $n$ space. Therefore $L(B)$ is empty iff $M$ doesn't halt.

$\endgroup$
4
  • $\begingroup$ can you kindly explain "whether 𝑀 halts on the empty input within 𝑛 space" part? $\endgroup$ – SiluPanda Apr 20 '19 at 15:37
  • 1
    $\begingroup$ The LBA can simulate the Turing machine on it’s available space, which is $n$ cells. If the Turing machine tries to use more space, it can just abort. $\endgroup$ – Yuval Filmus Apr 20 '19 at 15:46
  • $\begingroup$ So... if it does abort, then it means that this particular input needs more space? I'm trying to see where the contradiction happens. $\endgroup$ – sprajagopal Jan 15 at 12:43
  • $\begingroup$ If it aborts on an input in length $n$, then $M$ uses more than $n$ space. $\endgroup$ – Yuval Filmus Jan 15 at 13:22

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.