reduction - 可还原性 Etm 不可判定

Question

我想问一下减量。

在证明 Etm 在 M1 的定义中不可判定是

1.如果 x!=w，拒绝

2.如果 x==w，在输入 w 上运行 M，如果 M 执行，则接受

在我遇到的许多证明中，我看到了那条粗线，但我不明白我该怎么做，因为我不知道它是否会停止。

我会很高兴知道我错在哪里。

谢谢。

Answer 1

接受图灵机意味着停止接受配置。因此，如果您模拟 M 并且它接受，它将停止并且您将能够注意到这一点。

如果 M 没有停止，这意味着它不接受 w。在这种情况下，您也不应该接受。不接受的一种方式是永远奔跑。所以如果你对 M 的模拟永远运行，这会让你永远运行，这正是你应该做的。

因此，您无需知道 M 是否会停止。这不起作用。 在输入 w 上运行 M 并在无法计算M 拒绝时接受，因为您需要检测无限计算并接受它们的输入。