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?
$\begingroup$
$\endgroup$
-
$\begingroup$ Does this answer your question? Are Linear Bounded Automatons Turing Complete? $\endgroup$ – ttnick Jun 29 '20 at 15:23
-
$\begingroup$ @ttnick it answers partially $\endgroup$ – Vamsi Shankar Jun 29 '20 at 16:56
-
$\begingroup$ @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? $\endgroup$ – Vamsi Shankar Jun 29 '20 at 17:01
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ Can you give any example of such language which is rejected by LBA but accepted by a Turing machine? $\endgroup$ – Vamsi Shankar Jun 29 '20 at 16:58
-
$\begingroup$ 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? $\endgroup$ – Vamsi Shankar Jun 29 '20 at 17:02
-
-
$\begingroup$ 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$. $\endgroup$ – nir shahar Jun 29 '20 at 17:43
