Bri*_*les 7 theory complexity-theory automata turing-machines
有一种图灵机可以处理的语言,LBA不能,但有没有任何有用的实际问题,LBA无法解决,但TM可以解决？
LBA只是一台带有限磁带的图灵机器,实际的计算机存储空间有限,所以在我看来LBA无法做到的实际重要性. 除了线性有界自动机不仅仅是一个有限的磁带,而是一个大小与输入大小成线性函数的磁带这一事实.有限性的线性是否以某种方式限制了LBA？
是否存在LBA无法应对的问题,但是指数有界自动机可能(如果存在这样的话)？
我要勇敢地说“不”。我们今天使用的几乎每种编程语言都是上下文相关的。（实际上甚至上下文不敏感，仅比上下文无关 IIRC 稍强）。显然，如果我们不能对其进行编程，我们就不会真正关心它......
OTOH，这一切都取决于你对“有趣”的定义......阿克曼的函数显然属于这一类......这有趣吗？