5 Undecidability

5.1 Church-Turing Thesis

什么是算法？算法应该是一个强大的工具，能够完成特定的任务，一个真正的算法必须在所有输入下都能够终止。

所以半判定只能在接受的情况下停机，但是在一些输入下永远不会停止，那就不算真正意义上的算法

Church-Turing Thesis 指的就是任何可以被图灵机（Turing Machine, TM）计算，并且在所有输入上都最终停止的过程，都可以被称为‘算法’。我们直观地认为图灵机可解决的问题是可计算问题，不可解决的就是不可计算的问题。图灵机定义可不可计算的边界。

这个论断可以证伪

那么存在哪些问题是不可被计算的呢？这有利于我们探究计算的边界。比如说一个很经典的不可计算问题是 halting problem，这就意味着没有一个算法可以解决这个问题。

5.2 Universal Turing Machines

图灵机能否被“编程”？ 也就是是否可以设计一个图灵机来模拟其他任意图灵机的行为。

我们可以设计一台图灵机 U，输入为另一个图灵机 \(M\) 和输入串 \(w\)，使得 \(U\) 的输出与直接运行 \(M\) 在 \(w\) 上的结果相同，即：\(U(M,w)=M(w)\)

通过一种编码方法，把图灵机 \(M\) 的所有信息（如状态、字母表、转移函数等）表示成一个字符串。然后完成对该图灵机的模拟。编码的思路也比较简单，

状态用 q 开头，然后用二进制编码；字符用 a 开头，然后用二进制编码；转移关系用一个四元组来表示 \((q,a,p,b)\)，代表的含义是在状态 \(q\) 下读到 \(a\)，就进入 \(p\)，并将 \(a\) 改为 \(b\)。

Example

对于通用图灵机来说，我们的输入是图灵机 M 的编码结果以及输入 w

具体设计如下：

首先构造一个三带图灵机 \(U'\)，它有三条磁带，分别用于：

• 第一条：模拟被模拟图灵机 M 的工作磁带（即输入和计算过程）
• 第二条：存储图灵机 M 的完整编码（相当于“程序”）
• 第三条：记录当前状态（即 M 的当前状态）

计算过程（模拟步骤）：

• 输入为 “\(M\)" 和 “\(w\)”，其中 \(M\) 是某台图灵机的编码，\(w\) 是它的输入。
• 首先将 \(M\) 复制到第二条磁带上，把 \(w\) 写在第一条磁带的开头，第三条磁带写上起始状态 \(s\)。

• 然后逐步模拟 \(M\) 的运行：

  • 在第二条磁带上查找当前状态和读取符号所对应的转移规则（四元组）。

  • 根据该规则更新第一条磁带（修改内容、移动读写头）和第三条磁带（更新状态）。

• 重复上述过程，直到第三条磁带上出现终止状态（如 \(h\)），表示计算结束；也可能永远不结束。

5.3 The Halting Problem

接下来我们要寻找的是不可递归的语言，我们是知道这样的语言的是存在的，因为图灵机是可数无限的，而语言是不可数，所以这样不可递归的语言肯定是有的。

一个很常见不可计算问题的就是停机问题

我们称 \(H\) 是停机问题的形式化版本，这里的 \(H\) 指的是一个语言（language），定义如下：

\[ H=\{⟨M,w⟩∣图灵机 M 在输入 w 上停止\} \]

显然 \(H\) 应该是递归可枚举的，因为我们可以设计一个通用图灵机来半判定这个语言（模拟 \(M\) 的行为，输入 \(w\) 停机了就说明接受这个语言，不停机就不接受）

我们现在要说明的是 \(H\) 并不是递归语言，我们利用反证法来说明。假设 \(H\) 是可递归的，那么对于 \(H_1 = \{⟨M⟩:M 在输入 ⟨M⟩ 上停机\}\) 也是可递归的（从图灵机的角度考虑即可），那么由于递归对于补是封闭的，那么 \(\overline{H_1}\) 也是递归语言的，但是 \(\overline{H_1}\) 甚至都不是递归可枚举的。

证明过程：如果存在 \(M^*\) 半判定 \(\overline{H_1}\)，那么 \(⟨M^*⟩\) 到底属不属于 \(\overline{H_1}\)呢？如果属于，那么就说明 \(M^*\) 在输入为 \(⟨M^*⟩\) 时并不会停机，但是由于其属于 \(\overline{H_1}\)，而 \(M^*\) 半判定 \(\overline{H_1}\)，说明实际上是会停机的，这就发生矛盾了。相应的不属于的逻辑也是类似的，那么就说明根本就不存在这样的 \(M^*\)

我们接下来更是要说明的是 停机问题 \(H\) 是所有递归可枚举语言中 “最难” 的一个。如果它能被判定，那么所有递归可判断语言都能被判定；反之亦然。

假设停机问题 \(H\) 是递归的（即可判定），即存在图灵机 \(M_0\) 能判断任意 \(\langle M, w \rangle\) 是否停机。

那么，对任意半判定语言 \(L(M)\)（即 \(M\) 在 \(w\in L(M)\) 时停机接受，否则可能永不停机），我们可以构造一台新图灵机 \(M'\)：

1. 输入 \(w\)
2. 用 \(M_0\) 判断 \(M\) 在 \(w\) 上是否停机
3. 若停机 → \(w\in L(M)\)，\(M'\) 接受
4. 若不停机 → \(w\notin L(M)\)，\(M'\) 拒绝

因此，\(M'\) 能在所有输入上停机并正确判定 \(L(M)\)。

5.4 Undecidable Problems about TM

设\(L_1,L_2\subseteq\Sigma^*\)是语言。从\(L_1\)到\(L_2\)的归约是一个递归函数\(\tau:\Sigma^*\to\Sigma^*\)，满足：

\[ x\in L_1\quad\text{当且仅当}\quad\tau(x)\in L_2 \]

其实直白地来说就是 \(L_2\) 比 \(L_1\) 要难。如果

• \(L_2\) 是可判定的，那么 \(L_1\) 也是可判定的
• \(L_1\) 是不可判定的，那么 \(L_2\) 也是不可判定的

利用规约法，我们可以说明一个新问题与已知难解的问题具有相同的难度。

下列关于图灵机的问题都是不可判定的（undecidable）。

• 停机问题：给定一台图灵机 \(M\) 和一个输入串 \(w\)，问：\(M\) 在输入 \(w\) 上是否会停止？
• 空带停机问题：给定一台图灵机 \(M\)，问：\(M\) 在空输入带上是否会停止？

• 存在性停机问题：给定一台图灵机 \(M\)，问：是否存在某个字符串 \(w\)，使得 \(M\) 在 \(w\) 上会停止？

• 全局停机问题：给定一台图灵机 \(M\)，问：\(M\) 是否在所有输入串上都会停止？

• 两台机器等价停机问题：给定两台图灵机 \(M_1\) 和 \(M_2\)，问：它们是否在相同的输入串上都停止？
• 语言性质判断问题：给定一台图灵机 M，其半判定的语言为 \(L(M)\)，问：\(L(M)\) 是否是正则语言？\(L(M)\) 是否是上下文无关语言？\(L(M)\) 是否是递归语言（可判定语言）？
• 在某些特定的图灵机 M，使得仅判断它在不同输入 w 上是否停机，就已经是一个不可判定的问题。

上述这些问题应该怎么来证明呢？以空带停机问题为例

• \(H = \{'Mw' \mid M \text{ halts on } w\}\)
• \(L = \{'M' \mid M \text{ halts on } e\}\)
• \(f('Mw') = \text{the encoding of } M_w = \begin{cases}1.\ \text{If input } x \neq e,\ \text{reject}; \\ 2.\ \text{run } M \text{ on } w; \\ 3.\ \text{if } M \text{ halts, accept}.\end{cases}\)
• \('Mw' \in H \Rightarrow L(M_w) = \{e\} \Rightarrow f('M_w') \in L\)
• \('Mw' \notin H \Rightarrow L(M_w) = \varnothing \Rightarrow f('M_w') \notin L\)
• \(H \leq L\)

基本的思路首先列出需要规约的两个问题，表示为通用图灵机下的输入；然后构造一个函数，完成二者的转换。

5.5 Properties of Re. Languages

定理：语言 \(L\) 是递归的当且仅当 \(L\) 和其补集 \(L\) 都是递归可枚举的（r.e.）。

证明如下：

若 \(L\) 是递归的，则它一定是递归可枚举的（因为所有递归语言都是 r.e.）；同时，由于递归语言的补集仍是递归的，因此 \(L\) 也是递归的，从而也是 r.e.。

反之，若 \(L\) 和 \(L\) 都是 r.e.，则可以构造一个判定 \(L\) 的算法：对任意输入 \(w\)，同时运行 \(L\) 和 \(L\) 的半判定过程，由于 \(w\) 要么属于 \(L\)，要么属于 \(L\)，所以其中一个过程最终一定会停机；一旦停机，即可根据是哪个过程停机来决定接受或拒绝 \(w\)，从而实现对 \(L\) 的完全判定。因此，\(L\) 是递归的。

---

定义： 我们说图灵机 \(M\) 枚举语言 \(L\)，当且仅当存在 \(M\) 的某个固定状态 \(q\)，使得

\[ L = \left\{ w \mid (s, \triangleright \underline{\ }) \vdash_M^* (q, \triangleright \underline{\ } w) \right\} \]

即：从初始状态 \(s\) 和空白输入开始，经过若干步推导后，机器进入状态 \(q\) 且输出为 \(w\)。 一个语言是 图灵可枚举的（Turing-enumerable），当且仅当存在一台图灵机能够枚举它。

---

定理： 一个语言是递归可枚举的（recursively enumerable），当且仅当它是图灵可枚举的。

证明过程

⇒ 方向：递归可枚举 ⇒ 图灵可枚举 假设图灵机 \(M\) 半判定语言 \(L\) ，即对任意输入 \(w\) ，若 \(w \in L\) ，则 \(M\) 会停机接受；否则可能永不停机。我们构造一台新的图灵机 \(M'\) 来枚举 \(L\) 。其基本思想是系统地生成语言 \(L\) 的字母表上的所有字符串，并对每个字符串模拟 \(M\) 的运行。为了避免某个无限长的计算阻塞整个过程，采用“对角线并行”（dovetailing）策略：依次执行 \(M\) 在不同字符串上的前 1 步、前 2 步、前 3 步……这样可以确保只要 \(M\) 在某个字符串上最终停机，\(M'\) 就能在有限步内发现它，并将该字符串输出到输出带上。因此，\(M'\) 能够枚举出 \(L\) 中的所有字符串。

⇐ 方向：图灵可枚举 ⇒ 递归可枚举 反过来，假设图灵机 \(M\) 枚举语言 \(L\) ，即存在一个固定状态 \(q\) ，使得每当 \(M\) 运行到状态 \(q\) 时，输出带上就出现一个属于 \(L\) 的字符串。我们构造一台新图灵机 \(M'\) 来半判定 \(L\) ：给定输入 \(w\) ，\(M'\) 启动 \(M\) 并在空白带上运行。每当 \(M\) 经过状态 \(q\) 时，\(M'\) 暂停检查输出带上当前的字符串是否等于 \(w\) 。如果相等，则 \(M'\) 停机接受；否则继续模拟。由于 \(M\) 最终会输出 \(L\) 中的所有字符串，一旦 \(w \in L\) ，它一定会出现在输出带上，从而被 \(M'\) 发现并接受。因此，\(M'\) 半判定 \(L\) ，说明 \(L\) 是递归可枚举的。

定义： 设图灵机 \(M\) 枚举语言 \(L\)。我们称 \(M\) 按字典序枚举 \(L\)，如果以下条件成立（其中 \(q\) 是一个特殊的“输出”状态）每当 \((q, \triangleright \underline{\ } w) \vdash_M^+ (q, \triangleright \underline{\ } w')\) 时，字符串 \(w'\) 在字典序上严格位于 \(w\) 之后。

一个语言是 按字典序图灵可枚举的，当且仅当存在一台图灵机能够按字典序枚举它。

---

定理： 一个语言是递归的，当且仅当它是按字典序图灵可枚举的。

证明过程

⇒ 方向：递归 ⇒ 按字典序图灵可枚举
假设图灵机 \(M\) 决定语言 \(L\)，即对任意输入 \(w\)，\(M\) 总能在有限步内停机并接受或拒绝。我们构造一台新的图灵机 \(M'\) 来按字典序枚举 \(L\)。其基本思想是：\(M'\) 按字典序依次生成语言 \(L\) 字母表上的所有字符串，并将每个字符串作为输入交给 \(M\) 运行。如果 \(M\) 接受该字符串，则 \(M'\) 将其写入输出带上（通过进入“显示状态” \(q\)）；如果 \(M\) 拒绝，则 \(M'\) 不进入显示状态，直接跳到下一个字符串。由于 \(M\) 是决定器，它对每个输入都会停机，因此我们可以保证枚举过程是可控的。这样，\(M'\) 会以字典序输出 \(L\) 中的所有字符串，从而实现按字典序枚举。

⇐ 方向：按字典序图灵可枚举 ⇒ 递归
反过来，假设语言 \(L\) 被一台图灵机 \(M\) 按字典序枚举。若 \(L\) 是有限语言，则显然它是递归的（因为有限语言总是可判定的）。若 \(L\) 是无限语言，我们构造一台图灵机 \(M'\) 来决定 \(L\)：给定输入 \(w\)，启动 \(M\) 并等待其输出。\(M'\) 监控 \(M\) 的输出过程，直到出现以下两种情况之一：一是 \(w\) 被输出（即出现在显示状态），此时 \(M'\) 接受 \(w\)；二是某个字典序大于 \(w\) 的字符串被输出，此时 \(M'\) 拒绝 \(w\)。由于 \(L\) 是无限的，而比 \(w\) 小的字符串数量有限（最多为 \(|\Sigma|+1^{|w|}\)），因此必有一个事件会发生。于是 \(M'\) 总能在有限步内停机并做出正确判断，说明 \(L\) 是递归的。

下面我们介绍 Rice Theorem:

对于任意一个关于图灵机所识别语言的非平凡语义性质（即该性质不适用于所有递归可枚举语言，也不全都不适用），判定一台图灵机的语言是否具有该性质是不可判定的。换句话说，任何只依赖于图灵机语言内容（而非其具体结构或运行方式）且既非恒真也非恒假的性质，都无法通过算法自动判断。

比如说之前的空带停机问题，由于存在一些图灵机在空带上停机，也有不在空带上的停机的，所以这是非平凡的，所以这个问题是不可判定的。

但要注意的是 RIce 定理只适用于关于语义性质的问题，不能解决语法性质的问题。语法性质指的是这类性质依赖于图灵机的具体结构、状态数、转移规则或运行行为，而非其语言 \(L(M)\) 本身。

Rice 定理是判定一个语言是否可判断的利器

证明过程

假设存在一个图灵机 \(H\) 能判定某非平凡性质 S，即对任意图灵机 \(M_i\)，\(H\) 能判断 \(L(M_i)∈S\) 是否成立。我们选取两个语言：\(A∈S\) 和 \(B\notin S\)（由非平凡性保证其存在）。

给定任意图灵机 \(M\) 与输入 \(w\)，构造一个新的图灵机 \(M’\)，其行为如下：在输入 \(x\) 上，\(M'\) 并行模拟 \(M(w)\) 和 \(M_B(x)\)；若 \(M(w)\) 停机，则转而模拟 \(M_A(x)\)。于是：

• 若 \(M(w)\) 停机，则 \(L(M')=A∈S\)；
• 若 \(M(w)\) 不停机，则 \(L(M')=B\notin S\)。

因此，判断 \(L(M')∈S\) 等价于判断 \(M\) 在 \(w\) 上是否停机。若 \(H\) 存在，就能解决停机问题——矛盾。故原假设错误，\(S\) 不可判定。

Review

1. Classify whether each of the following languages are recursive, recursively enumerable but not recursive, or non-recursively enumerable. Prove your answers, but you may not simply appeal to Rice’s theorem.

(a) \(L_1 = \{\)“\(M\)”|\(M\) is a TM, and \(L(M)\) is uncountable\(\}\)

(b) \(L_2 = \{\)“\(M\)”| TM \(M\) accepts at least two strings of different lengths\(\}\)

Answer

(a) 所有语言都是可数的，\(L_1\) 是空集

(b) 可以构造一个图灵机 \(M'\) 来半判定该语言：\(M'\) 以交错模式运行 \(M\) 在所有可能的输入上，一旦发现 \(M\) 接受了两个长度不同的字符串，就停机并接受。因此 \(L_2\) 是递归可枚举的。

这个由莱斯定理很容易知道这个语言不是可判定的。考试的话我们需要定义一个归约函数 \(τ(⟨M⟩,x)=⟨M'⟩\)，其中 \(M'\) 的行为如下：对任意输入 \(w\)，若 \(∣w∣≤2\) 且原图灵机 \(M\) 在输入 \(x\) 上停机，则 \(M'\) 接受 \(w\)；否则 \(M'\) 不停机。这样，\(M\) 在 \(x\) 上停机当且仅当 \(⟨M'⟩∈L_2\)。由于停机问题是不可判定的，故 \(L_2\) 也不可判定，即不是递归语言。

2. The following problem is decidable: To determine, given a Turing machine \(M\) and a state \(q\), whether there is any configuration at all that yields a configuration with state \(q\).

Answer

这个问题是可判定的，题意是是否存在某一个配置可以进入 q 状态，实际上我们只需要检查转移关系，看是否有进入 q 的，如果有，那么相应的配置就是前一个即可。

3. The following problem is decidable: To determine, given a Turing machine \(M\), whether \(M\) ever writes a nonblank symbol when started on the empty tape.

Answer

这个图灵机有 \(s\) 个状态，模拟 \(M\) 在空带上的运行

• 在前 \(s\) 步内，\(M\) 写了一个非空白符号。则答案为 “是”。
• 在前 \(s\) 步内，\(M\) 从未写非空白符号。由于初始磁带全为空白，且 \(M\) 未写入任何非空白符号，因此磁带始终全为空白。由于只有 \(s\) 个状态，在 \(s+1\) 次移动中必有某个状态重复出现。但我们在前 \(s\) 步内未写非空白符，说明至第 \(s\) 步为止已访问了 \(s+1\) 个配置（包括初始），故至少有两个配置（这时配置只看状态，因为磁带上都是空）具有相同状态。因磁带内容处处相同（全空白），一旦状态重复，机器将进入无限循环，且永远不会写非空白符号。则答案是 ”否“。

那么对于这个问题你是否有疑问？为什么这个问题不能通过 Rice 定理来回答，如果通过 Rice 定理来看，有些图灵机会写非空白符，有些并不会，那么应该不能判断才对。但实际上这是不对的，因为这个性质并不是语言的语义性质，什么意思呢？也就是说这个图灵机是否接受这个语言不仅仅取决于这个语言，还取决于图灵机，这时我们不能通过 Rice 定理去判断

4. The following problem is decidable: To determine, given a Turing machine \(M\), whether there is some string \(w\) such that \(M\) enters each of its non-halting states during its computation on input \(w\).

Answer

根据 Rice 定理，很容易知道上述问题是不可判定的，因为总有一些图灵机满足有字符串遍历所有，也有一些图灵机无论什么字符来都不遍历。

构造一个归约函数 \(τ\)：对任意图灵机 \(M\)，构造新图灵机 \(M'\)，其添加一个新符号 \(σ\) 和一个新状态 \(q\)。\(M'\) 首先模拟 \(M\) 在输入 \(w\) 上的运行；若 \(M\) 进入停机状态，则 \(M'\) 转移到状态 \(q\)，写入 \(σ\)，然后从字典序最小的非停机状态开始，依次遍历所有非停机状态（跳过停机状态），每次写入 \(σ\)，最后进入状态 \(q\) 并停机。

这样就将上述问题规约到停机问题上了

5. \(A≤_m B\) and \(B\) is a regular language, then \(A\) is also a regular language.

Answer

1) 取 \(A = \{a^n b^n : n \geq 0\}\), \(B = a^*\)
2) 从 \(A\) 到 \(B\) 的归约：给定输入 \(x\)，如果 \(x = a^n b^n\)，则提取所有 \(a\)；否则返回 \(b\)

注意规约只用于 Recursive 和 R.E. 的判断，因为中间的转换函数限制在图灵机上可完成的，并不是在 FA 和 PDA 上的

6. Decide whether the language \(L= \{\)“\(M\)”: \(M\) is a Turing Machine and \(|L(M)| ≤ 3\}\) is Recursive or R.e. but not recursive or Not r.e.

Answer

Not r.e. 对于非递归可枚举语言的证明，只需要将停机问题的补集归约到这个语言上即可，因为停机问题的补集是非递归可枚举的

这个规约的过程常常是这样的

\(\overline{H} = \{'Mx':M \text{ not halts on } x\}\)，然后我们构造规约函数 \(f('Mw') =\) "\(M'\)"，其中 \(M'\) 经常就是舍弃当前输入，然后直接模拟 \(x\) 在 \(M\) 上的结果，然后再根据题目做出相应的调整。在这个题目中就直接模拟即可，不需要做调整。【调整的目的是为了满足下面这两个要求】

然后说明当 \('Mx'\in \overline{H}\) 的时候，\(M'\) 不会对任何输入停机，也就是说 \(L(M') = 0\)，那么显然 "\(M'\)" 属于 \(L\)

而当 \('Mx'\notin \overline{H}\) 的时候，\(M'\) 对任何输入停机，那么 \(L(M') > 3\)，那么显然 "\(M'\)" 不属于 \(L\)

如果将这个问题的 \(\le 3\) 改为 \(>3\) 就是 \(r.e.\) 了

7. Decide whether the language \(L = \{'Mx'\) is a Turing Machine \(x\) is a string, and there exists a TM，\(M'\), such that \(x\notin L(M) \cap L(M')\}\) is Recursive or R.e. but not recursive or Not r.e.

Answer

Recusive 这个问题的关键在于读懂题目，这个语言包含所有形如 ⟨M⟩⟨x⟩ 的输入对，满足以下条件：

• \(M\) 是一台图灵机，\(x\) 是某个字符串；
• 存在至少一台其他图灵机 \(M'\)，使得 \(x\) 不在 \(M\) 和 \(M'\) 都接受的字符串集合中。

那么这个其他图灵机就直接取一个什么都拒绝的图灵机即可，那么这时，\(x\) 可以随便取，这个 \(L\) 集合就是所有图灵机的集合

8. Decide whether the language \(L\) = {“\(M\)”: \(M\) is a Turing Machine and \(|M|\) ≤ 1000} is Recursive or R.e. but not recursive or Not r.e.

Answer

图灵机的编码是在某个固定的有限字母表上进行的，每个图灵机被编码为一个字符串，其长度最多为 1000。因此，所有可能的字符串长度 ≤ 1000 的数量是有限的。\(L\) 是一个有限语言（finite language）。所以 \(L\) 是可判定的

评论区

对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！