Example of language accepted by Turing Machine but not by Linear Bounded Automata ? Is there any EXPSPACE language?
Turing Machine Vs Linear Bounded Automata
2
$\begingroup$
computational-complexity
automata
formal-languages
1 Answers
4
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.
-
0I'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)$. – 2012-01-24