如何证明函数是不可计算的？
https://cs.stackexchange.com/questions/11181
-
16-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我知道如果可以计算功能，则存在图灵机。然后如何显示该功能是 不是 可计算或没有任何图灵机。有什么像抽动引理吗？
解决方案
在回答您的一般问题之前，让我首先退后一步，给一些历史背景，并回答一个初步问题：不可兼容的功能甚至存在吗？
符号注：我们可以将任何函数$ f $与语言$ l_f = {（x，y） mid y = f（x）} $相关$ f $
不确定的语言 做 存在
有些语言无法决定。该论点很简单：只有许多$（ aleph_0）$不同的TMS只有“仅”，但无数$（ aleph）$不同的语言。因此，最多有$ aleph_0 $可决定的语言，其余的（无限的）是不可决定的。进一步阅读：
为了将我们的手放在特定的不可确定的语言上，这个想法是使用一种名称的技术 对角度 （Georg Cantor，1873年）最初用来表明，比整数或换句话说，$ aleph> aleph_0 $的实际数字更多。
构建第一种不可决定的语言的想法很简单：我们列出了所有图灵机（这是可能的，因为它们是可重复枚举的！），并创建了一种与至少一个输入中每个TM不同意的语言。
$$ begin {array} {c | ccccc}＆ varepsilon＆0＆00＆00＆ cdots hline m_1＆ color {red} {1} {1}＆0＆1＆1＆1＆1＆1＆1 m_2＆0 ＆ color {red} {1}＆0＆0＆0 m_3＆0＆0＆ color {red} {0} {0}＆1＆0 vdots＆＆＆＆＆＆＆＆＆＆＆ end {array {array {array } $$
在上面，每一行是一个TM，每一列是一个输入。如果TM拒绝或永不停止，则单元格的值为0，如果TM接受该输入，则为1。我们将语言$ d $定义为使$ d $包含$ i $ th输入时，并且仅当$ i $ $ -th tm不接受该输入时。
在上表之后，$ varepsilon notin d $，因为$ m_1 $接受$ varepsilon $。同样，$ 0 notin d $，但是$ 1 in D $，因为$ m_3 $不接受$ 1 $。
现在，假设$ m_k $决定$ d $并在表中查找$ k $：如果$ k $ - th列中有$ 1 $，则$ m_k $接受该输入 但这不是在$ d $中, ，如果那里有$ 0 $，则输入为$ D $，但$ m_k $不接受。因此，$ m_k $不决定$ d $，我们达到了矛盾。
现在要问你的问题。有几种方法可以证明一种语言是不可决定的。我会尝试触摸最常见的。
1.直接证明
第一种方法是直接表明一种语言是不可决定的，可以证明没有TM可以决定它。术语上遵循上面所示的对角线化方法。
例子。
证明（补充）对角线语言$$ overline {l_d} = { langle m rangle mid mid langle m rangle rangle notin l（m）} $$是不可决定的。
证明。
假设$ Overline {l_d} $是可决定的，让$ m_d $为其决定者。有两种情况：
- $ m_d $接受$ langle m_d rangle $: ：但是，$ langle m_d rangle in L（m_d）$ so $ langle m rangle notin Notin inteLline {l_d} $。因此，如果$ m_d $决定$ overline {l_d} $，则不会发生这种情况。
- $ m_d $不接受$ langle m_d rangle $: ：so $ langle m_d rangle notin l（m_d）$，因此$ langle m rangle in intlline {l_d} $。但是，如果它是$ l_d $，则应该接受$ m_d $，我们再次达到矛盾。
2.关闭属性
有时，我们可以使用闭合属性来表明某些语言是不可决定的，我们已经知道我们已经知道不可决定的。
具体而言，如果$ l $无法确定（我们编写$ l notin r $），则其补充$ overline {l} $是不可决定的：如果有$ overline {l} $的decider $ m $只要每当$ m $拒绝时，就可以使用它来决定$ l $，反之亦然。由于$ m $总是停止答案（这是一个决定者），因此我们可以随时颠倒其答案。
结论：对角线语言$ {l_d} = { langle m rangle mid mid langle m rangle in L（m）} $是不可证实的，$ l_d notin r $。
可以通过指出，如果$ l $及其补充$ operline {l} $都是递归枚举的，则可以应用类似的论点。如果我们想证明一种语言不是递归列举的，而是不可证明的性能，那么这将特别有用。
3.从不确定的问题中减少
通常，很难直接证明一种语言是不可决定的（除非已经以“对角线”的方式构建）。证明不确定性的最后一个也是最常见的方法是使用另一种我们已经知道的语言。这个想法是将一种语言减少到另一种语言：要证明，如果一种语言是可决定的，那么另一种语言也必须是可决定的，但是其中一种已经众所周知，这是不可决定的，这得出了一个结论，即第一个也是不可决定的。阅读有关减少的更多信息 “什么是彼此减少问题的常见技术？”.
例子。
证明对角线语言$$ hp = { langle m，x rangle mid m text {halts on} x } $$是不可决定的。
证明。
我们知道$ l_d $是不确定的。我们将$ l_d $减少到$ hp $（这是表示$ l_d le hp $），也就是说，我们表明，如果$ hp $是可决定的，我们可以使用其决定者来决定$ l_d $，这是矛盾的。
减少的作用是通过将$ w $ for $ l_d $（即任何潜在的决定者/$ l_d $的受体输入）转换为$ hp $ $ hp $的$ w'$，以便在l_d $中$ w ，只有在hp $中的$ w'。我们确保此转换是可计算的。因此，确定$ w'$告诉我们是否在l_d $中$ w ，因此，如果我们可以决定HP，我们也可以决定$ L_D $。
转换如下。服用一些$ W = langle m rangle $，然后输出$ W'= langle m'， langle m rangle rangle rangle $，²其中$ m'$是tm，是一个像$ m $一样，但是如果$ m $拒绝，则$ m'$进入无限环路。
让我们看看$ w，w'$满足要求。
如果$ w in l_d $，则表示$ M $ 停顿 并接受输入$ langle m rangle $。因此，$ m'$也会停止并接受输入$ langle m rangle $。因此，$ langle m'， langle m rangle rangle in hp $。
另一方面，如果$ w notin l_d $，则$ m $要么拒绝或从不停止$ langle m rangle $。在这两种情况下，$ m'$都将在$ langle m rangle $上进入无限环路。因此，$ langle m'， langle m rangle rangle rangle notin hp $，我们完成了l_d $中的$ w in l_d $ in y in hp $ in l_d $ in in l_d $，因此显示了$ HP Notin r $。
进一步阅读：可以通过 减少 标签。
对减少的有效性还有更多的限制。转换本身必须是 可计算, ，并为任何输入定义良好。
$ hp $的输入看起来像$ langle m，x rangle $，其中$ m $为tm，$ x $是某个字符串。因此，在这里，我们选择字符串$ x $作为机器$ m $的编码，这只是一个字符串。
4.大米定理
“因此，每次我们希望证明$ l $是不确定的，我们都需要将$ l_d $（或$ hp $）减少到它吗？没有任何捷径吗？”
好吧，实际上，有。这是 赖斯的定理.
该定理说，许多具有一定结构的语言是不可决定的。因为所有这些语言都有这种特定的结构，所以我们可以减少一次并将其应用于任何接受类似结构的语言。
该定理按以下方式正式陈述，
定理（大米）。 给定 财产 $ emptySet subsetNeq s subsetNeq re $，以下语言$ l_s $是不可否认的$$ l_s = { langle m rangle rangle rangle reid l（m）l（m） in S } $$
集合$ s $是$ re $中的语言子集；我们之所以称其为属性，是因为它描述了接受语言$ l（m）$的属性。所有能够满足此属性的语言的TM属于$ L_S $。
例如，$ s $可以是接受语言$ l（m）$完全包含两个词的属性：
$$ s_2 = {l mid | l | = 2，l in re }。$$在这种情况下$ l_ {s_2} $是所有TMS的集合，其语言完全由两个单词组成：$$ l_ {s_2} = { langle m rangle rangle rangle rangle rangle 中l（m） in s } = { langle m rangle mid | l（m）| = 2 }。$$
该属性可能非常简单，但不能 全部 语言或 没有任何 语言。如果$ s = emptyset $或$ s = re $，则说该财产为 琐碎的, ，诱导的$ L_S $是可计算的。简单$ s $的一个示例是只包含一种单一语言，例如$ s_ {complete} = { sigma^*} $。请注意，尽管$ s $仅包含一种单一语言，但有无限的许多机器$ m $的语言为$ sigma^*$，因此$ l_ {s_ {s_ {vampee}} $是无限的，是不可能的。
该定理非常有力证明多种语言的不可证明性。
例子。
语言$ l_ emptySet = { langle m rangle text {永远无法确定
证明。
我们可以将$ l_ emptySet $作为$ { langle m rangle rangle mid l（m）= 0 } $，即$ l_ emptySet = l_s = l_s $ for property $ s = s = {l {l {l {l in Re ，| l | = 0 } $。这是一个非平凡的属性（它包括语言$ l = emptySet $，但不包括，例如，语言$ l = {1，11，11，111， ldots } $。因此，通过赖斯的定理，$ l_ emptyset $是不可决定的。
我们现在证明了定理。如上所述，我们将显示从$ HP $减少到$ L_S $（对于任何任意的非平凡$ S $）。
证明。
令$ s $为非平凡的属性，$ emptyset subsetneq s subsetneq re $。我们显示$ hp le l_s $，也就是说，我们将$ hp $减少到$ l_s $，这样，如果我们可以决定$ l_s $，我们将能够决定$ hp $（我们知道这是不可能的，因此，$ l_s $不能决定）。在下面的证明中，我们假设空语不是$ s $的一部分，即$ emptyset notin s $。 （如果空语是$ s $，则在补充属性$ overline s = re setminus s $上的等效证明作品，我将省略详细信息）。由于$ s $是非平凡的，因此它至少包括一种语言；让我们称呼该语言$ l_0 $，并假设$ m_0 $是接受$ l_0 $的机器（存在这样的机器，因为$ s $仅包含RE中的语言）。
回想一下，在这种减少的情况下（请参见上面的第3节），我们需要显示如何将$ hp $的输入$ W $转换为输入$ W'$ for $ l_s $，因此$ w in hp quad text {if and If} quad w' in l_s $$
让$ w =（ langle m rangle，x）$，我们将其转换为$ w'= langle m' rangle $，其中的描述机器$ m'$（在输入$ x'$上是以下：
- 在$ x $上运行$ m $。
- 如果步骤1上方停止，请在$ x'$上运行$ m_0 $，并相应地接受/拒绝。
我们看到这种转换是有效的。首先要注意，构建$ m'$的描述给定$ w =（ langle m rangle，x）$很容易。
如果$ w 在hp $中，则$ m $在$ x $上停止。在这种情况下，$ m'$将进入步骤2，并且行为就像$ m_0 $。因此，其接受的语言为$ l（m'）= m_0 在s $中。因此，$ w'= langle m' rangle in l_s $。
如果$ w notin hp $，则$ m $ loops on $ x $。这种情况，任何输入$ x'$上的$ m'$ loop 。因此，$ w'= langle m' rangle notin l_s $。
4.1扩展的大米定理
赖斯的定理为我们提供了一种简单的方法，可以证明满足某些属性的某种语言$ l $是不可决定的，即$ l notin r $。稻米定理的扩展版本使我们能够通过检查$ l $是否满足一些其他属性来确定该语言是否递归可恢复能力。
定理（大米，延长）。 给定的属性$ s subseteq re $，语言$$ l_s = { langle m rangle rangle mid l（m） in s } $ in in s } $$是递归增强的（$ l_s in re $） 当且只有 以下所有三个陈述共同持有
- 对于任何两个$ l_1，l_2 in re $，如果$ l_1 在s $中，以及$ l_1 subseteq l_2 $，则$ l_2 in s $。
- 如果$ l_1 在s $中，则存在有限的子集$ l_2 subseteq l_1 $，因此$ l_2 在s $中。
- 所有人的集合 有限 $ s $中的语言是枚举的（换句话说：有一个TM列举了所有有限语言$ l in S $）。
证明。
这是一个“且仅在”定理中，我们应该证明其两个方向。首先，我们证明，如果一个条件（1,2,3）不满，则$ l_s notin re $。之后，我们将证明，如果所有三个条件同时保持，则在re $中$ l_s 。
如果（1,2）持有，但（3）却没有，则$ l_s notin re $.
让我们假设$ l_s in Re $，我们将看到我们有一种方法可以接受$ s $中的任何有限语言（因此，所有这些语言的集合均为re），因此条件（3）保留和我们达到矛盾。如何确定有限的$ l $是否属于$ s $？很容易 - 我们使用$ l $的描述来构造仅接受$ l $单词的机器$ m_l $，现在我们运行$ l_s $ on $ m_l $上的机器（请记住 - 我们假设$ l_s in re $，因此有一台接受$ l_s $的机器！）。如果$ l 在s $中，则$ langle m_l rangle in l_s $，并且由于$ l_s in re $ in Re $，其机器会在输入$ langle m_l rangle $上说是，我们完成了。
如果（2,3）保留，但（1）不，则$ l_s notin re $.
我们假设$ l_s in Re $，我们将证明我们有一种方法来决定$ hp $，从而导致矛盾。
因为条件（1）无法保持，所以S $中有一种语言$ L_1 ，并且是一个超集，$ L_2 supseteq l_1 $，因此$ l_2 notin s $。现在，我们将重复第4节中使用的参数来决定$ hp $：给定输入$（ langle m rangle，x）$ for $ hp $，我们构造了一个机器$ m'$，其语言为$ l_1 $（如果$（ langle m rangle，x） notin hp $或其他方式，其语言为$ l_2 $。然后，我们可以决定$ hp $：$ x $上的$ m $ halts，或者$ l_s $的重新计算机接受$ m'$;我们可以并行运行，并保证至少一个会停止。
让我们提供构建$ m'$（输入$ x'$）的详细信息：
- 并行执行以下操作：
$ x $ 1.1运行$ m $。
1.2在$ x'$上运行$ L_1 $的机器 - 如果1.2停止并接受 - 接受。
- 如果1.1停止：在$ x'$上运行$ L_2 $的机器。
为什么这起作用？如果$（ langle m rangle，x） notin hp $，则1.1永不停止，$ m'$完全接受步骤1.2下接受的所有输入，因此$ l（m'）= l_1 $。另一方面，如果$（ langle m rangle，x）在hp $中，则在某个时候步骤1.1 halts和$ m'$完全接受$ l_2 $。可能会事先接受$ 1.2 $接受，但是由于$ L_1 subseteq l_2 $，因此在这种情况下，这不会改变$ m'$的语言。
如果（1,3）持有，但（2）却没有，则$ l_s notin re $.
同样，我们将假设$ l_s in re $ $ $，并表明$ hp $变得可决定，这是一个矛盾。
如果条件（2）不存在，则对于任何$ l_1 in s $中的任何有限子集$ L_2 subseteq l_1 $满足$ l_2 notin s $（请注意，$ l_1 $必须是无限的，因为$ l_1 subseteq l_1 $）。如上所述，为了确定给定输入$（ langle m rangle，x）$的$ hp $ ，x） notin hp $和一些有限的$ l_2 $否则。矛盾以与上述类似的方式遵循。
这台机器的构造与我们构建的以前的$ m'$非常相似。机器$ m'$（输入$ x'$）确实：
- 运行$ m $在$ x $上$ | x'| $ steps。
- 如果$ m $ $在步骤1中停止 - 拒绝
- 否则，在$ x'$上运行$ L_1 $的机器。
它认为，如果$（ langle m rangle，x）在hp $中，则在某个时候，例如在1000个步骤后，$ m $ $ $ halts on $ x $。因此，步骤1将停止（并拒绝）任何长度$> 1000 $的输入$ x'$。因此，在这种情况下，$ l（m'）$是 有限. 。另请注意，$ l（m'） subseteq l_1 $，尤其是根据条件（2）的无效性，我们有$ l（m） notin s $。
另一方面，如果$（ langle m rangle，x） notin hp $，则步骤1永不停止，我们从不拒绝步骤2。在这种情况下，很容易看到$ l（m）= l_1 $，尤其是$ l（m） in S $。
我们留下来显示扩展定理的另一个方向。也就是说，我们需要证明，如果所有条件（1,2,3）持有，那么我们有一个接受$ l_s $的TM，即，$ l_s in Re $。换句话说，我们需要显示一台机器$ m_s $，因此对于任何输入$ langle m rangle $，$ l（m）在s $中，机器接受此输入，$ m_s（ langle m rangle） to textsf {accept} $。
这是机器$ m_s $的行为方式（输入$ langle m rangle $）：
- 令$ m _ { text {enum} s} $是列举$ s $的所有有限语言的机器，根据条件（3）保证。
- 并行运行以下操作（通过欺骗，请参阅Eg， 这个 和 这个）$ i = 1,2，... $
2.1运行$ m _ { text {enum} s} $，直到输出语言$ l_i $
2.2。检查$ m $是否接受$ l_i $的所有单词（在这些单词上运行$ m $，同时并行）。
2.3。如果对于一些$ i $，$ m $接受$ l_i $的所有单词 - 接受。
为什么起作用？如果$ l（m）在s $中，则它在s $中具有有限的子集$ l_j ，一旦$ m _ { text {enum} s} $输出该子集，步骤2.2/2.3会发现$ M $接受该语言的所有单词并接受。
另一方面，如果$ l（m） notin s $，它不能接受任何$ i = 1,2，... $的$ l_i $中的所有单词。实际上，根据（1），任何$ l' supseteq l_i $也在$ s $中，因此，如果$ m $接受某些$ i $的$ l_i $中的所有单词l_i $，因此在s $中$ l（m），矛盾。
最后，请注意，以下是上述简单（非常有用的）推论：
推论（大米，延长）。 给定一个非琐事属性$ s subsetneq re $，因此$ emptySet in s $，语言$$ l_s = { langle m rangle rangle rangle reid l（m） in s } $递归可容纳，即$ l_s notin re $。
其他提示
一个有用的工具是 赖斯的定理. 。这就是它所说的：
令$ emptyset subsetneq p subsetneq mathcal {p} $一组非平凡的一组可计算的单一函数和$ varphi $ a 戈德尔编号 $ Mathcal {p} $的of。然后$ p $的索引集
$ qquad i_p = {i in mathbb {n} mid mid varphi_i in p } $
不是递归。
您发现它也以图灵机的编码（或任何其他图灵完整编程语言）表示，即$ i_p = { langle m rangle rangle mid m mathrm {tm {tm {tm {tm}，f_m in P } $ ;这里$ langle。 rangle $定义了Gödel编号。
也就是说，您可以使用Rice的定理来证明此类$ s $非恢复性，这些$ s $非恢复性是非平凡函数集的索引集（或降低为$ s $）。
请注意，有一个扩展名可以用来证明某些索引集并非递归枚举。
例子
令$ varphi $ agödel编号。考虑一组自然
$ qquad a = {i in mathbb {n} mid varphi_i（j）= 1 text {for All} j in 2 mathbb {n} } $。
现在因为$ p = {f in mathcal {p} mid f（j）= 1 text {for all} j in 2 mathbb {n}
- $ a = i_p $，
- $（n mapsto 1） in P $和
- $（n mapsto 2） notin p $，
可以应用稻米定理，并且$ a $是不可决定的。
由于许多人不熟悉Gödel编号，因此请注意，通过使用$ a = { langle m rangle mid f_m（x）= 1 text {for All } x in 2 mathbb {n} } $。
未示例
考虑一组自然
美元
当然是不可计算的。但是，$ a $不是任何$ p $的索引！令$ f = varphi_i $ for a $中的某些$ i 。因为$ varphi $是 戈德尔 编号，有（无限的）$ j neq i $带有$ varphi_j = f $，但对于所有$ j notin a $持有，因为$ f（2）= i neq j $。
警惕这个！根据经验，如果在“右侧”上使用该函数的索引，则在集合定义中用作函数的参数，则可能不是索引集。您可能需要 $ s_ {mn} $ 哥德尔编号的财产和 FIXPOINT定理 证明一组不是索引集。
