图灵机可以处理一些 LBA 无法处理的语言，但是有没有 LBA 无法解决但 TM 可以解决的有用的实际问题？
LBA 只是带有有限磁带的图灵机，而实际计算机的存储空间是有限的，因此在我看来，LBA 不能做任何具有实际重要性的事情。 除了 因为线性有界自动机不仅具有有限的带子，而且具有大小是输入大小的线性函数的带子。有限性的线性是否以某种方式限制了 LBA？
是否存在 LBA 无法解决但指数有界自动机可以(如果存在此类情况)的问题？
最佳答案
维基百科文章 context-sensitive languages指出任何递归
决策为 EXPSPACE 的语言(即可以被图灵机识别) -难的
不是上下文敏感的，因此不能被 LBA 识别。他们
举一个这样的语言的例子:包括幂运算的等价正则表达式对的集合。
关于theory - 与图灵机相比，线性有界自动机的有用限制是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2143204/