What are the useful limits of linear bounded automata compared to Turing machines?

There are languages ​​that the Turing machine can handle that the LBA cannot, but are there any useful practical problems that the LBAs cannot solve, but the TM can?

LBA is just a Turing machine with a finite tape, and actual computers have limited storage, so it seems to me that there is nothing practical that LBA cannot do. Except for the fact that a linear constrained automaton has not only a finite tape, but also a tape with a size, the linear function of which is the input size. Does limb linearity somehow limit LBA?

Are there any problems that the LBA cannot handle, but an exponentially bounded automaton can (if such things exist)?

+6
complexity-theory theory turing-machines automata
source share
2 answers

I'm going to step on a limb and say no. Almost every programming language we use today is context sensitive. (Actually not even context sensitive, just a little stronger than the free context, IIRC). And, obviously, if we can’t program it, it’s not very important for us ...

OTOH, it all depends on your definition of "interesting" ... Ackerman's function clearly fits into this category .... interesting?

+1
source share

A Wikipedia article for context-sensitive languages claims that any recursive language (i.e. recognized by a Turing machine) whose solution is EXPSPACE -hard is not context-sensitive and therefore cannot be recognized by LBA. They give an example of such a language: many pairs of equivalent regular expressions, including exponentiation.

+2
source share

All Articles