我最近遇到了停止问题矛盾的证明。在证明中，我们必须为图灵机提供程序的副本和输入的副本，以决定该程序是否停止输入。在矛盾中，为什么必须是程序作为程序和输入？对不起，如果听起来令人困惑。我可以简单地用程序和随机输入喂养机器，然后得出相同的结论。
谁能告诉我为什么？我没有想到的特定原因吗？
首先让我回到证明本身。
halt_tm是不可证实的
假设任何机器都有以字符串形式的描述。令HALT_TM = {<M, w>| M is a TM and M halts on input w}和A_TM = {<M,w>| M is a TM and accepts w}。在这里，我认为我们知道A_TM是不可决定的（证据可以通过对角度化来完成，并意识到，由于具有比图灵机的语言更多的语言，并且作为给定的TM只能决定一种语言，因此未决定使用某种语言）。
假设HALT_TM是可决定的，这意味着我们将Decider D用于此语言。然后，我们将能够构建决定A_TM的计算机M。在输入<M', w>上，M执行以下操作：
- 在输入
<M',w>上运行D - 如果
D拒绝，拒绝，否则在w上运行M'（直到停止它，我们知道这是因为D不拒绝！） - 如果
M'接受，请接受，如果拒绝，请拒绝。
在那里，我们看到了与我们的假设的矛盾
通用图灵机
现在，您的问题的核心：您实际上为M馈送任何有效的机器描述M'，不一定是<M>本身。请记住，TM和"一个程序"实际上是等效的：有关更多详细信息，请参见此不错的答案。引用相同的答案：" 图灵机是算法的正式类似物"。图灵机的一种力量是可以将它们编码为字符串，从而允许另一台图灵机（称为"通用图灵机"）执行它们。因为给定的机器是一种算法，所以您会发现您实际上正在喂食"顶级" TM程序，并且您选择的输入。