递归可枚举语言和莱斯定理¶

递归可枚举语言和递归语言¶

递归可枚举语言（RE）

$L=\{x|\exists y,\langle x, y\rangle \in R\}$ ，其中 $R$ 是递归语言

注意到，这个定义很像 $\textbf{NP}$ 的定义，即 $L=\{x|\exists y,\langle x, y\rangle \in \textbf{P}\}$ 。

莱斯定理（Rice's Theorm）¶

Rice's Theorm

RE语言的任何非平凡都是不可判定的。

RE语言的性质

RE语言的性质是RE语言的一个集合，如上下文无关性质，是由所有上下文无关语言组成的集合，即 $\{L|L是上下文无关语言，可由下推自动机判定\}$ 。更一般的，对RE中任何一个语言，均有图灵机可以识别，故性质也可以表示为图灵机的集合。

即RE的某个性质 $P$ 实际上是由一部分图灵机组成的集合，这些图灵机均判定相同的语言。特别注意，性质不要理解成图灵机本身的物理性质，如有几条读写带，有多少状态，读写头是否会向左走等。实际上，图灵机的这些物理性质，均是可判定的。

需要注意到对于某个语言，有无穷个图灵机判定，例如添加无用的状态，添加无用的读写带，均可使图灵机的编码发生变化。故 $P$ 是一个无穷集合，考虑到所有的图灵机是可数无穷的，故 $P$ 也是一个可数无穷集合。

非平凡性质

性质 $P$ 是非平凡的：存在 $\langle M_1\rangle \in P$ ，存在 $\langle M_2\rangle \not\in P$ 。

判定某个图灵机是否具有平凡性质是可计算的：若该平凡性质包含所有图灵机，则判定器输出是；若该平凡性质是空集，则判定器输出否。

为何判定某个图灵机是否有性质P是困难的¶

直觉上，判断图灵机是否识别语言 $L$ ，需要将所有可能的输入验证一般。然而有无穷多可能的输入（如 $\{0,1\}^*$ ），故永远都验证不完，即不会停机。例如，若 $L$ 是空语言，则需要验证对于所有输入，图灵机均拒绝。

注意到验证某个机器接收空语言，对有穷自动机和下推自动机均是可判定的。而Rice定理告诉我们，对于图灵机是不可判定的。那么就有疑问，能否用有穷自动机，判断某个有穷自动机接收空语言。另一方面，是否存在一个更强的机器，能够判断图灵机是否接收空语言。对于前一个问题，笔者猜测答案是否。需要将有穷自动机表示为字符串，而对于空语言的有穷自动机，他们的字符串表示需要写成一个正则表达式，这似乎不太可能。对于后一个问题，由丘奇图灵论题，不存在比图灵机更“强”的机器。

Rice定理的证明¶

下面证明Rice定理。

我们需要证明：对任意性质 $P$ ，语言 $\{\langle M\rangle | \langle M\rangle \in P\}$ 均不可判定。

首先假设空语言不属于 $P$ ，即 $P$ 中的所有图灵机，均会接收某串，不存在图灵机对所有串拒绝或死循环。

由于 $P$ 非平凡，故存在 $\langle M_p\rangle \in P$ 。

下面我们将停机问题归约到 $P$ 。即将停机问题的某个输入 $(\langle M\rangle, w)$ 转化为 $\langle M'\rangle$ ，通过判定 $\langle M'\rangle$ 是否在 $P$ 中，即可判定 $(\langle M\rangle, w)$ 是否在停机问题中。

构造 $M'$ 如下：

接受输入 $x$
模拟运行 $M$ ，其模拟输入为 $w$
若 $M$ 停机，则模拟运行 $M_p$ ，其模拟输入是 $x$ ，返回结果

其中若 $M$ 在输入 $w$ 时死循环，则会一直在上述步骤2中，即 $M'$ 死循环。

若 $\langle M'\rangle\in P$ ，则表示 $M$ 在输入 $w$ 时停机。否则，不停机。

若空语言属于 $P$ ，则空语言属于 $\bar{P}$ ，则 $\bar{P}$ 不可判定。由于递归语言是补封闭的，故 $P$ 不可判定。