-3
$\begingroup$

I have read that linear bounded automaton is a Non deterministic Turing machine. Why is it so?

$\endgroup$
  • $\begingroup$ Could you point a link to where you've read this? I don't know much about LBAs, but I do know that all Non-deterministic turing machines can be converted into deterministic ones. So it's possible that the LBA to NTM conversion is intuitive, and what you were reading assumed the reader would realize that it implied it was a DTM as well. I could be wrong though. $\endgroup$ – jmite Mar 22 '14 at 2:40
  • $\begingroup$ Note that we don't know whether NLBA have more power than DLBA. That's probably why special emphasis is put on the non-determinism part of the definition. $\endgroup$ – Raphael Mar 22 '14 at 11:11
3
$\begingroup$

The definition of LBA (for example given in Wikipedia) is a non-deterministic Turing machine which uses linear space. So an LBA is a (space-restricted) non-deterministic Turing machine by definition. There could be other, equivalent definitions.

$\endgroup$
-1
$\begingroup$

If we are saying non deterministic Turing machine and LBA are same then its wrong. If we say non deterministic Turing machine with limited space then we can call it as LBA. LBA has space boundaries where as Turing machine don't have.

$\endgroup$
  • 2
    $\begingroup$ Can you explain what this answer adds over the existing one that warrants pinging people over five years later? $\endgroup$ – Raphael Nov 20 at 18:15

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.