Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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


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.