automata - 通过机器及其描述作为停机问题的输入是什么意思？

Question

在停机问题的证明中，为什么我们必须将机器及其描述作为输入传递？

例如，我可以通过机器的描述和其他一些输入（不是机器本身），但矛盾的证明仍然有效。

例如，假设 H(a, b) 如果 a 确实在“b”上停止，则给出答案“是”，否则给出“否”。

现在我们创建另一台机器“H*”，它的作用与 H 的作用相反。

H 停止意味着 H* 进入无限循环，而 H 不停止意味着 H* 停止。

现在不是通过 H(H*, H*); 如果我通过了 H(H*, X) 那么这意味着如果 H* 没有在 X 上停止，H* 将停止，反之亦然（它仍然是矛盾的证明）。

我不一定看到传递 H(H*, H*) 而不是仅仅传递 H(H*, X) 的想法。在后一种情况下，证明不工作吗？

标签： automataturing-machinescomputability

Answer 1

例如，假设 H(a, b) 如果 a 确实在“b”上停止，则给出答案“是”，否则给出“否”。

现在我们创建另一台机器“H*”，它的作用与 H 的作用相反。

关键是这并不总是可能的。正如停止问题所示，递归可枚举语言不会在补码下关闭。因此，对于它们的某些补码，不存在这样的 H*，例如对于停机问题。

构建 H* 的问题是检测 H 何时进入无限循环。没有算法可以做到这一点。尽管如此，H* 原则上可能存在；但是停止问题是可以证明不存在枚举 TM 的集合的一个例子。

如果课程在补语下关闭，那么您的论点可能会通过。