How is the emptiness of Linear Bound Automata (LBA) i.e $L = \{B \mid L(B) = \emptyset \}$ is undecidable?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Apr 20, 2019 at 14:38
-
$\begingroup$ can you kindly explain "whether 𝑀 halts on the empty input within 𝑛 space" part? $\endgroup$ Commented Apr 20, 2019 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$ Commented Apr 20, 2019 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$ Commented Jan 15, 2021 at 12:43
-
$\begingroup$ If it aborts on an input in length $n$, then $M$ uses more than $n$ space. $\endgroup$ Commented Jan 15, 2021 at 13:22