There are languages ββthat the Turing machine can handle that the LBA cannot, but are there any useful practical problems that the LBAs cannot solve, but the TM can?
LBA is just a Turing machine with a finite tape, and actual computers have limited storage, so it seems to me that there is nothing practical that LBA cannot do. Except for the fact that a linear constrained automaton has not only a finite tape, but also a tape with a size, the linear function of which is the input size. Does limb linearity somehow limit LBA?
Are there any problems that the LBA cannot handle, but an exponentially bounded automaton can (if such things exist)?
complexity-theory theory turing-machines automata
Bribles
source share