关于图灵机的无法确定的问题

本文概述

在本节中，我们将讨论有关图灵机的所有不确定的问题。减少量用于证明给定语言是否可取。在本节中，我们将首先了解归约的概念，然后我们将在这方面看到一个重要的定理。

归约是一种技术，其中，如果将问题P1简化为问题P2，则任何P2的解决方案都可以解决P1。通常，如果我们有一种算法可以将问题P1的实例转换为具有相同答案的问题P2的实例，则将其称为P1简化P2。因此，如果P1不是递归的，则P2也不是递归的。同样，如果P1不可递归枚举，则P2也不可递归枚举。

定理：如果将P1简化为P2，则

证明：

考虑P1的实例w。然后构造一个算法，使该算法将实例w作为输入并将其转换为P2的另一个实例x。然后应用该算法检查x是否在P2中。如果算法回答“是”，则意味着x在P2中，类似地，我们也可以说w在P1中。由于我们在还原P1之后获得了P2。同样，如果算法回答“否”，则x不在P2中，这也意味着w不在P1中。这证明了如果P1不可确定，则P1也是不可确定的。
我们假设P1是非RE，但P2是RE。现在构造一个将P1减少到P2的算法，但是通过该算法，P2将被识别。这意味着如果输入为P2，将会有一个图灵机说“是”，但是对于不在P2中的输入，可能会或可能不会停止。众所周知，可以将P1中w的实例转换为P2中x的实例。然后应用TM检查x是否在P2中。如果x被接受，那也意味着w被接受。如果w在P1中，则x也在P2中，如果w在P1中，则x也不在P2中，此过程描述了一个语言为P1的TM。这证明了如果P1是非RE，那么P2也是非RE。

有空和非空两种语言。令Le表示空语言，而Lne表示非空语言。令w为二进制字符串，Mi为TM。如果L（Mj）=Ф，则Mi不接受输入，则w在Le中。同样，如果L（Mj）不是空语言，则w用Lne表示。因此我们可以说

Le = {M | L（M）=Ф} Lne = {M | L（M）≠Ф}

Le和Lne互为补充。