# Are Linear Bounded Automatons Turing Complete?

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

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

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.

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.