theory - 与图灵机相比，线性有界自动机的有用限制是什么？

Question

有些语言是图灵机可以处理而 LBA 不能处理的，但是否有任何 LBA 无法解决但 TM 可以解决的有用的实际问题？

LBA 只是一个带有有限磁带的图灵机，而实际的计算机具有有限的存储空间，所以在我看来，没有什么是 LBA 做不到的。 除了线性有界自动机不仅有一个有限的磁带，还有一个大小是输入大小的线性函数的磁带。有限性的线性是否以某种方式限制了 LBA？

是否存在 LBA 无法解决的问题，但指数有界自动机可以（如果存在此类问题）？

Answer 1

我要四处走动，说“不”。我们今天使用的几乎每种编程语言都是上下文相关的。（实际上甚至不区分上下文，仅比上下文无关，IIRC 稍强）。显然，如果我们不能对其进行编程，我们就不会真正关心它......

OTOH，这一切都取决于您对“有趣”的定义......阿克曼的功能显然适合这一类......这很有趣吗？

Answer 2

上下文相关语言的维基百科文章指出，任何决定为EXPSPACE -hard的递归语言（即图灵机可识别）都不是上下文相关的，因此不能被 LBA 识别。他们给出了这种语言的一个例子：一组对等的正则表达式，包括求幂。