Problem Detail: I have read that linear bounded automaton is a Non deterministic Turing machine. Why is it so?
Asked By : user5507
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/22919 Ask a Question Download Related Notes/Documents
