Show that emptiness and finiteness are unsolvable for linear bounded automata, I didn't understand, Can anyone help me out?
Solving emptiness means you can determine whether or not a linear bounded automata accepts anything at all and solving finiteness means you can determine whether or not a linear bounded automata accepts a finite set.
The proof that emptiness for linear bounded automata is unsolvable depends on the fact that it is also unsolvable for Turing machines.
For every Turing machine, there is a linear bounded automaton that accepts the set of strings which are valid halting computations for the Turing machine.
If a Turing machine accepts nothing, then the set of strings which are valid halting computations is empty. The linear bounded automata which accepts this Turing machine's halting computations will also accept nothing. If it were possible to determine whether or not a linear bounded automata accepts nothing, then it would be possible to determine whether or not a Turing machine accepts nothing, but this is a contradiction, because it is not possible to tell whether or not a Turing machine accepts nothing.
The proof for finiteness being unsolvable for linear bounded automata is the same. If the set a Turing machine accepts is finite, a linear bounded automaton accepts this finite set. If it were possible to determine if a linear bounded automaton accepts a finite set, it would also be possible to determine if a Turing machine accepts a finite set, but this is a contradiction, because it is impossible to tell whether or not a Turing machine accepts a finite set.
These problems are unsolvable for Turing machines because only trivial set properties are solvable for the computable sets. The set K = { i | M_i(i) halts } is unsolvable, and finiteness and emptiness can be reduced to the set K, which is why they are unsolvable for Turing machines.