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)?

Evie

There are TM's that currently exceed 1 BFs (BigaFlops). Theoretically, you can't get much faster than that! – Lothair

@Robert Lamb: very funny, but my question was serious. Since a TM can't be built, we need some reference point if we're going to ask about "practical" problems. – Coelom

@Coelom For speed I'd say 10^x state transitions per second is reasonable, with x = 9 +/- 3. – Evie

@Coelom umm, why would we ever ask about "practical" problems on a Turing Machine? If we're at the TM level, we're in the world of theory, and "practical" is a word to be avoided B-) – Searle

I was too late to get my answer in, but my point was that the question is biased. "Practical" was Bribles' word, and a TM can beat LBAs only when tackling huge classes of problems, and then only by taking many steps. There are questions in quantum physics we know how to answer but it would take too long; a TM could tackle all of these (unlike any LBA) but the sun would burn out first. – Coelom

@Coelom You can still post an answer. And it can still be upvoted. – Evie

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?

Searle

You're saying Ackerman's function cannot be computer by an LBA? – Evie

I'm pretty sure that Ackerman's is PSpace hard, so yeah it's not LBA computable... It's actually Primitive Recursive Complete, which means that it's even harder than PSPACE... – Searle

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.

Coastal

I was looking for problems other than accepting/rejecting recursive or recursively enumerable languages. – Evie

@Bribles: It's hard to provide a well-supported, self-contained answer to your question without making some sort of argument that the proffered problem is (a) decidable, yet (b) not computable with a LBA. And reducing a computational problem to a language decision problem is the go-to technique for this sort of argument! – Coastal

A related question is whether Turing equivalence for a programming language or abstract machine is necessary for the real world, or if LBA equivalence would suffice. I wonder if there's something useful in the difference between a linear bounded automata and a merely finite automata. Is there something an exponentially bounded automata could do that a linear one can't that would matter to non-theoreticians? – Evie

Most games are PSPACE-complete, including Go, Chess, and Mahjongg. If the p is higher than 1 (and these seem to be) then they cannot be solved on a LBA. – Shammer

@Jim -- "recursive language (that is, recognizable by a Turing machine)" -- actually recursive languages are a subset of those that can be recognized by a TM, specifically they can be recognized by a TM that halts for all input. A general TM might not halt for some input and is associated with recursively enumerable languages (a superset of recursive languages). – Lothair

@Brian Postow, when I wrote "merely finite automata", I meant non-linear bounded automata. – Evie