turing-machines - 万能图灵机 U 应确定 M(x) 是否停止

Question

所以我们有一个通用图灵机 U，它应该确定输入 x 的图灵机 M 是否会停止。解决方案应以伪代码形式呈现。

有人可以帮我解决一下，我应该解决谁？

Answer 1

这听起来像是停止问题：

停机问题可以表述如下：“给定一个任意计算机程序的描述，决定该程序是完成运行还是永远继续运行”。这相当于在给定程序和输入的情况下决定程序在使用该输入运行时最终会停止还是永远运行的问题。

Alan Turing 在 1936 年证明，不可能存在解决所有可能的程序输入对的停止问题的通用算法。证明的一个关键部分是计算机和程序的数学定义，即所谓的图灵机。停机问题在图灵机上是不可判定的。

所以不，这是不可能的。

如果你愿意，你可能可以继续运行M一段x时间。如果它停止，我们就知道它停止了。如果它不停止，我们真的不知道它是否停止。