从 $HALT$ 减少到 $A_{TM}$

Question

我知道减少到从 $A_{TM}$ 到 $暂停$. 。但是是以下减少 从 $暂停$ 到 $A_{TM}$ 正确的？

我们正在寻找总的可计算函数 $f$ 映射自 $暂停$ 到 $A_{TM}$。以下TM $F$ 计算减少量 $f$.

F = on input <T, w>
    create the following TM T':
    T' = on input v:
       start T on v
       if T accepts or rejects, *accept*
    return <T',w>

我认为这条线 if T accepts or rejects, *accept* 是正确的，但如果有人可以检查这一点，那就太好了。

编辑：我找到了以下幻灯片，但我认为其中的结构不正确： http://slideplayer.com/slide/13791105/

Answer 1

有多种“减少”概念。您已经正确描述了 多一还原 的 $暂停$ 到 $A_{TM}$. 。您链接到的减少（更具体的链接 这里) 是一个 真值表约简. 。这些是更一般的对象（因此您的结果更强）。每一个又都包含在更广泛的概念中 图灵还原.

虽然多一约简通常是复杂性理论中的默认概念，但图灵约简及其结果 学位结构 是可计算性理论中的默认值。请注意，如果我想做的只是证明某个集合的不可判定性，那么从某个已知的不可判定集合进行图灵约简就足够了。

---

首先，让我们明确回顾一下所涉及语言的定义：

• $A_{TM}=\{\langle M,w angle:百万元 停止并接受输入 $w\}$.

• $HALT=\{\langle M,w angle:百万元 输入时停止 $w\}$.

您建议的减少 $暂停$ 到 $A_{TM}$ 是 正确的:给定 $M$, ，我们可以通过计算方式建造一台新机器 $\帽子{M}$ 它精确地接受那些字符串 $M$ 停止。（基本上，只需替换中的所有“拒绝”状态 $M$ 通过“接受”状态。）

---

现在让我们看看您链接到的其他减少（更具体的链接 这里).

基本上，链接的参数不是“所有停止状态都接受”，而是单独考虑：

• 原始机器，以及

• 当原始机器拒绝时，“相反”机器会准确地接受，反之亦然。

对任一情况的肯定回答 $A_{TM}$ 确保原机器得到肯定的回答 $暂停$.

从我的头脑中，我认为没有理由这样做而不是遵循你的论点，特别是因为它产生的结果较弱，但它是正确的，足以证明幻灯片中更广泛的主张，即 $A_{TM}$ 是不可判定的。