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.


1 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).

  • $\begingroup$ In his book, Sipser uses the fact the determinisitc LBA have a finite number of configurations to prove that the membership for deterministic LBA is decidable. My questions is: can the same argument be used to prove that membership is decidable also for non-deterministic LBA (since its number of configurations is also finite)? If so, how this can be done? $\endgroup$
    – Marcus
    Commented Jun 2 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.