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

views:

240

answers:

+3 Q:

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

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

+1 A:

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.

Jim Lewis 2010-01-27 00:46:12

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

Bribles 2010-01-27 04:35:01

@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!

Jim Lewis 2010-01-27 08:02:06

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?

Bribles 2010-01-27 15:06:17

@Bribles, you don't mean Finite automaton, you mean unbounded TM...

Brian Postow 2010-02-24 16:57:44

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.

Joel 2010-02-24 17:05:09

@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).

Robert Lamb 2010-02-24 17:31:37

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

Bribles 2010-02-25 00:51:44

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?

Brian Postow 2010-02-24 17:02:35

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

Bribles 2010-02-25 00:47:12

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...

Brian Postow 2010-02-25 14:53:53

ansaurus

tags:

views:

answers:

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

related questions