一些进一步的例子

做减法是一种技能，就像其他任何技能一样——练习是有帮助的。在深入研究第五章的问题之前，您会发现再看几个例子会有所帮助。在这些笔记中，我将展示一些额外的映射约简示例，然后引导您完成第五章练习中另外三个问题的解决方案。

停止TM是不可判定的

这里我们证明了ATM≤m HALTTM。

对于我们的第一次尝试，我们尝试平凡映射f( ) = 。这是失败的，因为很可能有一个例子，M不接受一些w，但M仍然停在w上。这个例子中， 不在ATM中，但 在HALTTM中。

一个有效的映射是将 映射到 ，其中N是以下机器：

输入x：

  1. 模拟x在M上运行。
  2. 如果M接受x，停止并接受。
  3. 如果M拒绝x，就永远运行下去。

这个映射是有效的，因为如果 在ATM中，N将在w上停止，如果 不在ATM中，那么N将在步骤1中永远运行，或者在步骤3中永远运行：在这两种情况下 都不在HALTTM中。

ETM是不可判定的

这里我们证明了ATM≤m ETM。

对于我们的第一次尝试，我们尝试平凡映射f( ) = 。这是失败的，因为如果 在ATM中，则M接受至少一个输入，因此M不可能在ETM中。

第一次失败的尝试表明，我们实际上应该做的是试图证明ATM≤m ETM。

朴素映射f( ) = 在这种情况下也失败了，因为如果 不在ATM中，可能仍然存在其他y，使得M接受y，这导致M不在ETM中。

一个有效的映射是说f( ) = ，其中N是以下机器：

输入x：

  1. 如果x≠w，停止并拒绝。
  2. 模拟M在x上运行，如果M运行，则接受。

如果我们可以使用这个映射来显示ETM是不可确定的，那么它立即可以得出ETM是不可确定的。

问题四

如果A≤m B，且B是一种规则语言，是否可以得出A是规则语言？

不：设A是任意图灵可判定的非正则语言，设A是B的任意表示，B是B的任意表示。

输入x：

  1. 在x上运行A的决定论。
  2. 如果决定器接受，则输出a。
  3. 如果决定器拒绝，则输出b。

在这个答案中需要注意的一件有趣的事情是，从A到B的映射甚至不必是远程映射。我们完全没有义务去映射到B的每一个元素——在这个答案中，我甚至没有尝试去做。

问题15

考虑一个问题，确定输入w上的图灵机M在w上计算的任何时刻是否试图将其磁带头向左移动。将其表述为一种语言，并表明它是可决定的。

L = { | M在操作输入w时将其磁带头向左移动}

这是一个有趣的问题，因为第五章主要是关于证明眼前的一切都是不可决定的。这与事实相差不远，因为几乎赢博体育涉及图灵机一般行为的问题都是不可确定的。为了证明一些涉及图灵机行为的语言是可决定的，我们必须在手头的问题中寻找一些特殊或不寻常的东西。

这里我们利用了这样一个事实，即如果图灵机永远不会将其磁带头向左移动，那么它在运行到输入字符串的末尾之前只能运行这么长时间。这让图灵机处于一种我们可以利用的特殊情况。

以下是决定者将做的事情：

当输入 时：

  1. 模拟M在w上运行b| w|步。
  2. 如果模拟将磁带头移动到左边的任何点，则停止并接受。
  3. 如果模拟已达到停止状态，则停止并拒绝。
  4. 请注意我们停止模拟时机器所处的状态。为M构造一个新的控件，该控件具有与以前相同的状态，但只保留尝试读取空白的转换。此外，标记赢博体育从它们那里读取空白并向左移动的过渡状态。
  5. 从机器停止的状态对修改后的控件运行宽度优先搜索算法。如果搜索能够达到标记状态之一，则停止并接受。否则，停止并拒绝。

这个解决方案的关键是，一旦磁带磁头跑过输入的末端，我们就在一个简化的环境中操作了。在这种状态下，机器只会遇到空白，直到它决定向左移动。这一观察结果使我们能够极大地简化控制，并将控制变成一个简单的有向图。在这样一个图中搜索一个允许我们向左移动的状态是足够简单的，BFS可以处理它。

关于识别器

到目前为止，我们主要讨论了语言的决定器。如你所知，我们还有另一种选择，识别器。一种语言的有效识别器只需要接受机器识别的语言中的每一个输入。当我们向识别器提供非语言输入时，它可以停止并拒绝，也可以永远运行下去。这是一个方便的漏洞，使得构建识别器比构建决策器更容易。

ATM是不确定的，这意味着我们不能为它建立一个决策器。然而，我们可以很容易地为它建立一个识别器：

当输入 ：

  1. 模拟w在M上运行，直到它停止。
  2. 如果M接受w，停止并接受。
  3. 如果M拒绝w，停止并拒绝。

这是一个有效的ATM识别器，因为如果我们向它提供ATM的输入，它将接受。如果我们给它一个输入，而第一步一直运行，我们的机器已经隐式地拒绝了输入，这是它应该做的。

这也是我上次展示的一个关键定理的识别器版本：

定理如果A≤m B且B是图灵可识别的，则A是图灵可识别的。

这是a的识别器：

对于输入x，其中是a的一个潜在元素：

  1. 计算f (x)
  2. 在f(x)上运行B的识别器
  3. 因为A≤米 B我们有这个f（x)∈B当且仅当x ∈ 一个。如果识别器为B接受f（x)，它的意思是f（x)∈B，因此x ∈ 一个。我们停下来接受。
  4. 同样，如果B的识别器拒绝f(x)，这意味着f(x)不在B中，因此x不在a中。我们停止并拒绝。

这台机器允许另一种可能性：第二步可以永远运行下去。在这种情况下，B的识别器隐式地说f(x)不在B中，这意味着x不在A中，在一个不在A中的输入上永远运行是A的识别器允许做的事情。

最后，令人沮丧的事实是，有些语言甚至连图灵都认不出来。其中一个例子就是语言EQTM。无论是那种语言还是它的补充，图灵都认不出来。证明这一点的方法是从ATM到EQTM进行约简。由于ATM的补集不能被图灵识别，因此EQTM的补集的补集（EQTM本身）也不能被图灵识别。

这是实现可计算的f(x)的机器，它将ATM简化为EQTM。

当输入 ：

  1. 构造机器米1它拒绝了赢博体育的输入。
  2. 制造一台机器米2忽略输入，进行模拟w上运行的米，做什么？米所做的。
  3. 返回pair <米1 , 米2>。

问题22

证明A是图灵可识别的当且仅当A≤m ATM。

如果A≤m ATM，则定理5.28允许我们得出A是图灵可识别的。

如果A是图灵可识别语言，我们使用它的识别器R来构造从A到ATM的以下映射：

输入x：

  1. 返回对

映射是琐碎的，并且显然是可计算的。

如果x在A中，R将接受x，并且配对 落在ATM中。

如果x不在A中，则R不接受x，且对 落在ATM的补码中。