Undecidability of emptiness of LBA How is the emptiness of Linear Bound Automata (LBA) i.e $L = \{B \mid L(B) = \emptyset \}$ is undecidable?
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.