关于图灵机的不可判定问题

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

还原

规约是一种技术，如果一个问题 P1 规约为一个问题 P2，那么 P2 的任何解决方案都会解决 P1。 总的来说，如果我们有一个算法，将问题 P1 的一个实例转换为问题 P2 的一个实例，并且这两个实例的答案相同，那么它被称为 P1 规约 P2。 因此，如果 P1 不是递归的，那么 P2 也不是递归的。 类似地，如果 P1 不是递归可枚举的，那么 P2 也不是递归可枚举的。

定理：如果 P1 规约为 P2，那么

1. 如果 P1 是不可判定的，那么 P2 也是不可判定的。
2. 如果 P1 不是 RE，那么 P2 也不是 RE。

证明

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

空语言和非空语言

有两种类型的语言：空语言和非空语言。 设 L_e 表示一个空语言，L_ne 表示非空语言。 设 w 是一个二进制字符串，Mi 是一个 TM。 如果 L(M_j) = Ф，那么 Mi 不接受输入，那么 w 在 L_e 中。 类似地，如果 L(M_j) 不是空语言，那么 w 在 L_ne 中。 因此我们可以说

L_e = {M | L(M) = Ф}
L_ne = {M | L(M) ≠ Ф}

L_e 和 L_ne 互为补集。