赖斯定理

赖斯定理指出，图灵机识别的语言的任何重要语义属性都是不可判定的。属性 P 是所有满足该属性的图灵机的语言。

正式定义

如果 P 是一个非平凡的属性，并且持有该属性的语言 L p被图灵机 M 识别，则 L p = {<M> | L(M) ∈ P} 是不可判定的。

描述和属性

  • 语言的属性 P 只是一组语言。如果任何语言属于 P (L ∈ P)，则称 L 满足属性 P。

  • 如果一个属性不被任何递归可枚举语言满足，或者如果它被所有递归可枚举语言满足，则该属性被称为平凡的。

  • 一些递归可枚举语言满足非平凡属性，而其他语言则不满足该属性。形式上来说，在一个非平凡的属性中，其中 L ∈ P，以下两个属性都成立：

    • 属性 1 - 存在识别相同语言的图灵机 M1 和 M2，即 ( <M1>, <M2> ∈ L ) 或 ( <M1>,<M2> ∉ L )

    • 属性 2 - 存在图灵机 M1 和 M2，其中 M1 识别语言，而 M2 不识别，即 <M1> ∈ L 和 <M2> ∉ L

证明

假设属性 P 是非平凡的且 φ ∈ P。

由于P 是非平凡的，因此至少一种语言满足P，即L(M 0 ) ∈ P , ∋ 图灵机M 0。

令 w 为特定时刻的输入，N 为图灵机，如下 -

输入 x

  • 在 w 上运行 M
  • 如果 M 不接受（或不停止），则不接受 x（或不停止）
  • 如果 M 接受 w，则在 x 上运行 M 0。如果M 0接受x，则接受x。

映射实例 ATM 的函数 = {<M,w>| M 接受 N 的输入 w}，使得

  • 如果 M 接受 w 并且 N 接受与 M 0相同的语言，则 L(M) = L(M 0 ) ∈ p
  • 如果 M 不接受 w 并且 N 接受 φ，则 L(N) = φ ∉ p

由于A TM是不可判定的并且它可以简化为Lp，所以Lp 也是不可判定的。