# Turing Machine Vs Linear Bounded Automata

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

-

## 1 Answer

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.

-
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