# Undecidability of emptiness of LBA

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

• Thanks for the edit. Apr 20 '19 at 15:38

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.
• 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. Apr 20 '19 at 15:46
• If it aborts on an input in length $n$, then $M$ uses more than $n$ space. Jan 15 at 13:22