首先是上面的问题是否正确？
我认为可判定性是特定问题的属性，例如 1. 给定字符串是否属于特定语言 2. TM 是否会在给定输入上达到特定状态，而不是 TM（或任何其他机器）本身。
如果上述问题是正确的，那么我认为它是不可判定的。
它可能会停留在特定状态并且可能无法达到目标状态。它还可以修改输入并移动到以前的状态，所以我们也不知道它是否会达到目标状态
有什么方法可以证明或反驳它？
问问题
67 次
1 回答
0
根据 Rice 定理，如果输入 TM 是否具有某种语义属性，则如果该语义属性是非平凡的，则该输入 TM 是否具有不可判定性。语义属性是描述 TM 接受的语言的属性。如果某些 TM 但不是所有 TM 都为真，则语义属性是非平凡的。
一个 TM 是否具有无限多的状态不是 TM 的语义属性。这是一个关于 TM 结构的问题，而不是 TM 接受的语言。因此，赖斯定理不适用。
实际上，根据定义，图灵机只有有限多个状态。因此，这是一个微不足道的句法属性：所有 TM 都有有限数量的状态。具有有限数量状态的 TM 语言的决策者简单地转换到 halt_accept。
现在，人们可以想象一个类似 TM 的东西，它有无限多的状态，并且可以在磁带上输入无限大的输入，然后询问这些东西中的另一个是否可以决定这些东西是具有有限还是无限多的状态。如果您有兴趣追求这种思路，您可能需要考虑对于具有无限多状态的 TM 来决定具有无限大输入的问题意味着什么。超计算是一个术语，用于描述以这种方式工作的各种机器。但这些不是 TM。
于 2020-12-01T16:05:29.950 回答