Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape.
But this causes them to not be Turing Complete? Why?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
A linear bounded automaton is a Turing machine that runs on input of size $n$ in $\mathcal{O}(n)$ space. By the space hierachy theorem there exist languages that need e.g. $\omega(n^2)$ space.
$\begingroup$
$\endgroup$
You know that Turing machines can accept languages that aren't recursive.
A linear bounded automaton (LBA) running on word $\omega$ has a finite tape at it's disposal, so the total number of configurations (tape contents, head position, state) is finite. For a given word $\omega$ you can go through all possible computations of the automaton (by the above, there is a finite number of computations that don't lead to loops) and check if it accepts or not. Thus LBAs accept only recursive languages. Turing machines are strictly more powerful.
