0
$\begingroup$

Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape.

But this causes them to not be Turing Complete? Why?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.