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

递归语言（decidable）要求存在一个满足如下要求的图灵机：

  • Halt on accept
  • Halt on reject
    但是递归可枚举语言（RE:Recursive enumerable）要求存在的图灵机只需要满足：
  • Halt on accept
    换言之，对于 True RE可能存在某个句子，你不知道这个句子在图灵机上会不会停机

正规定义：

  • 递归可枚举语言是指由图灵机定义的语言（不管是通过终止状态接受还是通过停机接受）
  • 递归语言：
    • 定义算法是一个图灵机，该图灵机通过终止状态接受，并且无论接受与否，它都注定会停机
    • 定义递归语言是由 定义的，且 是一个算法

可判定性

对于图灵可判定和图灵可识别，这两个概念如下：

  • 如果一个语言是 递归语言 那么这个语言是 图灵可判定语言
  • 如果一个语言是 递归可枚举语言 那么这个语言是 图灵可识别语言

非递归可枚举语言

这种类型的语言是存在的，因为RE的集合是可数集合，但是所有语言的集合的势势不可数的

P 和 NP

P 是指存在一个单带、确定性的图灵机，能够在多项式时间内判定

NP是指，存在一个非确定性图灵机，能够在多项式时间内判定

注意这两者和上面的递归可枚举的区别，这里要求的都是判定，即一定是要停机的，这两个都是递归语言的子集

对于一个 来说，它的NTM的运行的树的最大高度不超过 即最坏的一条路也一定会在多项式时间内判出来

对于 NP 问题有一个很重要的定理，即

如果语言 属于 当且仅当它可以表示为：

其中 ，判定 的多项式时间图灵机 称为验证机

该定理的意思是，如果一个问题是 的，那么当且仅当，对于某个具体的解，存在多项式时间的判定方法

规约

规约的定义

可以被映射规约到 ，写作 ，如果存在一个可计算的函数 ，使得所有的 :

那么 被称作一个从 到 的规约

可判定的规约

如果 且 是可判定的，那么 也是可判定的

RE的规约

如果 且B是RE，那么 也是RE

注意规约的方向，假设我们现在已知问题 OLD 是一个不可判定的问题，我们想证明 NEW也是一个不可判定的问题，那么思路应该是：

  • 假设 NEW 是可判定的
  • 使用NEW的判定机来判定OLD
  • 从而证明OLD也是可判定的
  • 导出矛盾，证明NEW是不可判定的

各种封闭性

交 并 补 拼接 星闭包 同态 逆同态
正则 是 是 是 是 是 是 是
CFG 否 是 否 是 是 是 是
Decidable 是 是 是 是 是 否 是
RE 是 是 否 是 是 是 是

各种反例如下：

CFG在交下不封闭

和 的交是 不是CFG

CFG在差集下的性质

由于 所以在差集下也不封闭

递归语言在同态下不封闭

对于递归语言，如果同态是 那么对于 就有无穷种可能性，所以不能判定

递归可枚举语言在补集下不封闭

这是定义，因为在不接受的情况下无法知道是否停机

规约套路

对于语言的性质 ，构造 ，他的输入是字符串 ，对于一个 问题的实例，即

准备工作如下：

  • 首先，对于语言性质 找一个实例 ，例如，对于性质 接受的语言集合是无穷集合 ，该实例可以是 接受所有字符串
  • 找到实例 的一个子集 ，使这个子集不满足性质 ，例如 接受空集

构造 ：

  • 在输入 时直接接受，否则进入下一步
  • 如果上一步没有接受，那么运行 作为子过程，如果停机，那么 再接受

那么 具有性质 当且仅当 在 上停机

那么，由于性质 是可判定的，假设存在判定机 ，那么对于停机问题实例 的时候，根据上面的构造 ，由于判定机的存在，有：

  • 如果 那么accept
  • 如果 那么reject

所以就证明了 所以不可判定

以 $F = L = \{ | M \text{接受的集合是无穷集合} \}$ 为例

首先，构造 为接受所有的字符串，再构造 为不接受任何字符串，开始套公式：

构造 ：

  • 暂时不接受，也不拒绝
  • 如果上一步没有接受，那么运行 作为子过程，如果停机，那么 Accept

那么 具有性质 当且仅当 在 上停机

那么，由于性质 是可判定的，假设存在判定机 ，那么对于停机问题实例 的时候，根据上面的构造 ，由于判定机的存在，有：

  • 如果 那么accept
  • 如果 那么reject

所以就证明了 所以不可判定

以 $L = \{ | M \text{接受的语言是正则语言}\}$ 为例

首先，构造 为所有字符串，构造 为接受形如 的字符串

构造 ：

  • 接受所有形如 的字符串，如果这一步没有接受也不拒绝
  • 如果上一步没有接受，那么运行 作为子过程，如果停机，那么 直接Accept

那么 具有性质 当且仅当 在 上停机

那么，由于性质 是可判定的，假设存在判定机 ，那么对于停机问题实例 的时候，根据上面的构造 ，由于判定机的存在，有：

  • 如果 那么accept
  • 如果 那么reject

所以就证明了 所以不可判定

易错点

RE转NFA

记得在星闭包的时候，去的那条边上面也要加 因为星闭包可以直接啥也没有

写RE

记得考虑有限字符串，例如，以 结尾的字符串，在这个例子中，需要考虑 这三个特殊情况

注意分别是RE还是递归不可枚举

看一下能不能用NTM搞出证据来accept，如果只能搞出reject的证据，那么这个不是RE