What are the useful limits of Linear Bounded Automata compared to Turing Machines?

Question

There are languages that a Turing machine can handle that an LBA can't, but are there any useful, practical problems that LBAs can't solve but TMs can?

An LBA is just a Turing machine with a finite tape, and actual computers have finite storage, so it would seem to me that there's nothing of practical importance that an LBA can't do. Except for the fact that a Linear Bounded Automaton has not just a finite tape, but a tape with a size that's a linear function of the size of the input. Does the linearity of the finiteness restrict the LBA in some way?

Are there problems that a LBA can't cope with, but an Exponentially Bounded Automaton could (if such things exist)?

Answer 1

I'm going to go out on a limb and say "no". Pretty much every programming language that we use today is context sensitive. (Actually not even context sensitive, only slightly stronger than context free, IIRC). And obviously, if we can't program it, we don't really care about it...

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

Answer 2

The Wikipedia article for context-sensitive languages states that any recursive language (that is, recognizable by a Turing machine) whose decision is EXPSPACE-hard is not context-sensitive, and therefore cannot be recognized by a LBA. They give an example of such a language: the set of pairs of equivalent regular expressions including exponentiation.