Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Example of language accepted by Turing Machine but not by Linear Bounded Automata ? Is there any EXPSPACE language?

share|improve this question

1 Answer 1

Consider the language of pairs $(n,T)$ where $n$ is an integer and $T$ is a description of a Turing machine that, when started on an empty tape, eventually moves farther than $2^n$ squares away from the origin.

The empty language is in EXPSPACE. Wikipedia's EXPSPACE article mentions a known EXPSPACE-complete problem.

See also the space hierarchy theorem which gives a simple diagonal construction of languages tailored to have specific space complexities.

share|improve this answer
    
Henning: Are the two parts of the question independent? Or, in part (2), does the OP want an example of a language accepted by a TM and not by a LBA, with the additional restriction that it is in EXPSPACE? I am unable to tell. (It seems to me you have implicitly assumed that it is the former; is that right?). –  Srivatsan Jan 24 '12 at 23:08
    
@Srivatsan: Good point. I didn't consider that the second question could be an additional restriction. It is not much of a restriction, though -- even my outrageous example here is in EXPSPACE, if $n$ is assumed to be input in unary. –  Henning Makholm Jan 24 '12 at 23:18
    
I'd like to emphasize the space hierarchy theorem: it implies that exponential space is unnecessary for TM to be more powerful than a LBA, there are languages recognizable in $O(n \log n)$ space but not $O(n)$. –  sdcvvc Jan 24 '12 at 23:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.