映射减少以补充$ _ {tm} $

Question

我有一个关于映射减少的一般问题。我已经看到将功能还原为$ a_ {tm} $的几个示例

其中$ a_ {tm} = { langle m，w rangle： text {for} m text {是一台Turing Machine，它接受String} w } $

这非常适合证明不可证明性。但是说我想证明无法识别性。也就是说，我想使用给定$ a le_ {m} b $的推论，如果$ a $无法识别，那么$ b $是无法识别的。

因此，对于任何任意不认可的语言$ c $，可以简化为$ overline {a_ {a_ {tm}} $（任何示例语言都足以示例），我如何减少$ overline {a_ {a_ {tm}}} le_ {m} c $？

为了简单起见，仅在$ overline {a_ {tm}} $中仅考虑tm。

编辑

为了进行澄清，$ overline {a_ {tm}} = { langle m，w rangle：m text {是一台不接受字符串} w } $的图灵计算机

Answer 1

让我们以$ l _ { emptySet} = { langle m rangle mid l（m）= emptyset } $，也就是说，所有不接受单词的机器（即语言为空）。

现在，我们显示还原$ overline {a_ {tm}} le l_ emptyset $。减少是通过服用输入$（ langle m rangle，w）$的$ overline {a_ {a_ {tm}} $并将其转换为输入$ { langle langle tilde m rangle} $ for $ l_ emptyset $，这样

$（ langle m rangle，w） in intline {a_ {a_ {tm}} quad text text {iff} quad langle langle tilde m rangle rangle in l _ { emptyset} $$

给定$（ langle m rangle，w）$，我们可以以以下方式构造$ tilde m $。 $ tilde m $输入y执行以下操作：

1. 删除胶带
2. 在磁带上写$ w $
3. 在$ W $上运行$ m $，并且执行相同的操作（如果接受$ m $，则$ tilde m $也接受）。

说服自己可以从$ m $和$ w $的编码中构建$ tilde m $的编码。现在，让我们验证这种减少是有效的：

• 如果$（ langle m rangle，w） in overline {a_ {tm}} $，则$ m $要么拒绝或不停止。如果是这样，那么对于任何输入$ y $，$ tilde m $不接受$ y $。这意味着$ l（ tilde m）= emptyset $ so $ langle tilde m rangle in l _ { emptySet} $。
• 如果$（ langle m rangle，w） notin edine {a_ {tm}} $，则$ m $接受$ w $，因此$ tilde m $接受$ y $（每$ y $）。因此，$ l（ tilde m）= sigma^*$，这意味着$ langle tilde m rangle rangle notin l _ { emptyset} $。

“ iff”条件保留，我们成功地将$ overline {a_ {tm}} $的输入映射到$ l_ emptySet $的输入中。在这种情况下，我们说我们将$ overline {a_ {tm}} $减少到$ l_ emptyset $。也就是说，如果我们可以解决$ l_ emptySet $，我们还可以通过首先转换输入，然后运行在转换后的输入上求解$ l_ emptyset $的算法来求解$ overline {a_ {a_ {tm}} $。

Answer 2

您无法显示，对于不可识别的语言$ c $，$ overline {a_ {tm}} leq_m c $。如果$ OVERLINE {a_ {tm}} leq_m c $，则尤其是$ c $的图灵度大于或等于$ overline {a_ {a_ {tm}} $的图灵度暗示杜松子酒可降低。 $ overline {a_ {tm}} $的图灵度为$ 0'$，与$ a_ {tm} $的图灵度相同。有很多无法识别的语言，其图灵学位与$ 0'$无与伦比（既不大也不小于$ 0'$）。

Ran G.给出了工作的示例，因为$ l_ emptySet $特别是$ m $ - 等效于$ overline {a_ {tm}} $。有一个普遍的现象，即大多数“自然”问题往往在$ m $ -Begree中彼此相提并论。但是，如果您查看任意问题，这将不再正确。