turing-machines - 为什么决策程序 D 在使用决策程序 H 作为子程序时表现相反？

Question

根据所示段落，决策者 D 如何使用 H 作为子例程以及它的行为如何相反？

如果有人澄清这一点会非常有用吗？

Answer 1

如果图灵机在给定输入的情况下以接受状态结束，则称图灵机接受输入。如果它以任何其他状态结束，它会拒绝。

因此，如果我们有一台H接受输入的机器，<M, <M>>那么我们可以通过添加新的起点、将其作为输入<M>、构建<M, <M>>然后将其提供给其余部分来增强它H。这台新机器H*将与 相同H，但输入不同。如果我们现在切换接受和拒绝状态，我们将拥有机器，它将作为输入<M>并返回与 相反的结果H，这同样是D。