Number of configurations, non-deterministic $LBA$ and $A_{LBA}$

Question

The membership problem $A_{LBA}$ for a deterministic $LBA$ is decidable because the number of configurations that a $LBA$ can assume is finite. Since this number is also finite for a non-deterministic $LBA$, how can this information be used to show that the membership problem $A_{LBA}$ is decidable for a non-deterministic $LBA$?

Thanks in advance, Marcus.

P.S. Suppose the $LBA$ has $|Q|$ states, the size of the input is $|w|$ and the size of the alphabet is $|\Gamma|$. Then the number of possible configurations for this $LBA$ is $|Q|*(|w|+2)*|\Gamma|^{|w|}$. So it is finite.

Answer 1

That is correct. A LBA uses bounded space and this can be used to simulate all possible computations (on a fixed input). It is not even necessary to keep track of loops in the simulation, just cutting off at a maximum length of the computation will do.

There is a connection to Savitch's theorem which states that nondeterministic space can be simulated by deterministic space at the cost of squaring the space: $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}(f(n)^2)$. Relevant here is that LBA are linear space TM's. Thus according to the theorem, a nondeterministic LBA can be simulated by a quadratic space deterministic TM. It is not known whether nondeterministic LBA can de determinized (meaning we do not need the squaring).