theory - 证明确定性 LBA 是否接受无限数量的输入是不可判定的

Question

确定性线性有界自动机 (LBA) 是一种单带 TM，它不是允许将其头部移过输入的右端(但它可以在该部分上读取和写入最初包含输入的磁带)。

如何证明确定性 LBA M 是否接受无限数量的输入是不可判定的？

Answer 1

给定一个图灵机 M 和一个字符串 w，您可以证明以下语言被某些 LBA 接受:

L = { x#y | x is a computation trace of M accepting w and y is any string }

直观上，LBA 可以通过执行以下操作来检查这一点:

• 如果 x 语法不正确，则拒绝。
• 如果 x 未在正确的初始配置中启动，则拒绝。
• 如果计算跟踪的任何步骤不正确，则拒绝。
• 如果 x 是一条显示 M 拒绝 w 的迹线，则拒绝。
• 否则接受

TM 可以构建执行此操作的 LBA 的描述。

如果 M 接受 w，则该语言是无限的，因此 LBA 将接受无限多个输入。如果M不接受w，那么这个语言就是空的。因此，如果TM可以决定LBA是否有无限语言，它就可以决定M是否接受w，与这是不可能的相矛盾。

希望这有帮助!