# Difference between linear bound automata and a Turing machine

Can anyone give an example where a language can be rejected by linear bounded automata and accepted by a Turing machine. Is there any proof that a linear bounded automata is less powerful than a Turing machine?

• Does this answer your question? Are Linear Bounded Automatons Turing Complete? – ttnick Jun 29 at 15:23
• @ttnick it answers partially – Vamsi Shankar Jun 29 at 16:56
• @ttnick can i say that one of the difference is there will be no epsilon on the LHS side of productions of LBA but in a turing machine, epsilon productions can exist on the LHS side? – Vamsi Shankar Jun 29 at 17:01

Notice that linear bounded automata are precisely all TM's who use $$O(n)$$ space.
Now, by the space-hierarchy theorem, for any $$f$$ where $$n=o(f)$$ (for an extreme example, $$f(n)=2^n$$) we would have $$DSPACE(O(n))\subsetneq DSPACE(O(f))$$.
Thus there are languages who require space complexity bigger than $$O(n)$$, and therefore are not solveable by linear bounded automata but can be solved by a ($$O(f)$$ space) turing machine.
• And for an example, take a look at the proof: It builds a language in $O(f)$ that is not in $O(g)$, for $g=o(f)$. In our case, $g(n)=n$. – nir shahar Jun 29 at 17:43