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

Question

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

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

Answer 1

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

L = { x#y | x 是 M 接受 w 的计算轨迹，y 是任何字符串 }

直观地说，LBA 可以通过执行以下操作来检查这一点：

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

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

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

希望这可以帮助！