1
$\begingroup$

Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get why all the sources mentioned that it needs a NTM. I am not getting why I need a NTM for LBA? We also know that any NTM can be converted to DTM. Therefore, I can take a DTM and put those tape constraints for building a LBA. I think that with a tape constraints DTM would be converted to LBA! Please make me correct and kindly tell me why I need an NTM for an LBA?

$\endgroup$
2
$\begingroup$

The conversion from nondeterministic Turing machine to deterministic Turing machines doesn't conserve space. The best known construction, known as Savitch's theorem, converts a nondeterministic Turing machine using space $s(n)$ to a deterministic one using space $O(s(n)^2)$, and this is suspected to be tight in general; see for example this question on cstheory.

Linear-bounded automata correspond to a class of grammars, context-sensitive grammars, in the following strong sense: a language can be described by a context-sensitive grammar iff it is accepted by some linear-bounded automaton. We only know how to prove this result if the linear-bounded automata are allowed to be nondeterministic. Indeed, assuming that $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ (a conjecture which is much weaker than the tightness of Savitch's theorem), there exists a context-sensitive language which cannot be decided by a deterministic linear-bounded automaton.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

From Savitch's theorem:

A nondeterministic L(n)-tape bounded Turing machine can be simulated by a deterministic $[L(n)]^2$-tape bounded Turing machine, provided $L(n) \geq \log_2 n$.

Thus, in particular, every context-sensitive language can be recognized within deterministic storage $n^2$, where $n$ is the length of the input.

The context-sensitive languages are precisely those sets accepted by nondeterministic Turing machines within storage $L(n) = n$. Then Every context-sensitive language is accepted by some deterministic Turing machine within storage $n^2$.

Conclusion: So, this is all about a matter of storage, that is why we use NTM in the LBA as it requires less storage over DTM. As an interesting aside, there remains an open problem to do with LBAs in the realm of complexity theory: does a deterministic LBA have the same power as a normal non-deterministic LBA or, equivalently, does NSPACE(n) = DSPACE(n)?

N.B: Please make me correct if I misunderstand the concepts. If it is satisfactory then you may please give me an upvote.

Ref:

  1. Savitch, Walter J. "Relationships between nondeterministic and deterministic tape complexities." Journal of computer and system sciences 4.2 (1970): 177-192.

  2. https://www.cs.auckland.ac.nz/~nies/Students/Bax380project2010.pdf

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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