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⟩ 上停机\}\) 也是可递归的（毕竟这个语言是 \(H\) 的一个子集）那么由于递归对于补是封闭的，那么 \(\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 上是否停机，就已经是一个不可判定的问题。

评论区

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