# 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 '20 at 15:23
• @ttnick it answers partially – Vamsi Shankar Jun 29 '20 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 '20 at 17:01

## 1 Answer

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.

• Can you give any example of such language which is rejected by LBA but accepted by a Turing machine? – Vamsi Shankar Jun 29 '20 at 16:58
• 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 '20 at 17:02
• What do you mean by epsilon productions? – nir shahar Jun 29 '20 at 17:39
• 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 '20 at 17:43