我一直在阅读，并且试图了解在修整机方面的减少。这就是我的理解：这意味着它将问题 A 简化为问题 C。但我不太确定它是如何工作的。让我们看一个例子：
给定语言 L：
L ={<M,D>| M is s TM and D is a DFA so that L(M) = L(D)},
使用归约如何证明Atm < L.
我的解决方案：
M 是一个图灵机，它接受任何字符串并在该字符串上停止。D 是 DFA hast 接受语言 L 及其等效于 TM M。 Atm 是一个 TM, M 接受字符串w。
你怎么能证明使用直接减少Atm < L??
我们需要证明 L 的判定器可用于判定 Atm 的实例，即 L 的判定器可用于回答“给定的 TM 是否接受给定的输入字符串？”的问题。
给定一个<M, w>Atm 的实例，我们需要将它转换为这个问题的一个实例<M', D>，以便这个问题的解决方案能够回答另一个问题。
首先，构造M'使得L(M') = L(M) intersect {w}. 这可以如下进行。创建一个 TM 来扫描输入磁带并确保这w是输入。如果w不是输入，则停止拒绝。否则，返回磁带的前面并转换到以前的初始状态M。然后，M正常运行。显然，这只能接受w，因为我们拒绝了其他所有内容；如果M接受w，这也是如此，因为在初始阶段M正常运行之后。
其次，构造D使得L(D) = {w}. 这DFA将具有|w| + 2状态：初始状态、死状态和 中的每个符号一个状态w。
L现在，在实例上使用我们的决策者<M', D>。当且仅当 时，它才会停止接受，只有当which 反过来仅在contains时才满足时L(M') = L(D) = {w}才有可能。因此，如果我们停止接受，那么我们就有了Atm 实例的答案。L(M) intersect {w} = {w}L(M)w<M, w>