1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the edit. $\endgroup$ – SiluPanda Apr 20 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$
  • $\begingroup$ can you kindly explain "whether 𝑀 halts on the empty input within 𝑛 space" part? $\endgroup$ – SiluPanda Apr 20 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 at 15:46

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.