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

递归语言（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是不可判定的