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

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

递归可枚举语言（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\)不可判定。