什么是递归和递归可枚举语言？

在学习计算理论(TOC)中的递归可枚举语言之前，让我们先了解递归语言的概念。

递归语言

如果 L 是某个图灵机 (TM) 接受的在每次输入时停止的字符串集，则语言 L 是递归的（可判定的）。

例子

当图灵机达到最终状态时，它会停止。我们也可以说当 M 达到状态 q 和要扫描的当前符号“a”时，图灵机 M 停止，因此 δ(q, a) 是不确定的。

有些 TM 永远不会以任何一种方式在某些输入上停止，因此我们区分了 TM 接受的语言，该语言在所有输入字符串上都停止，而 TM 永远不会在某些输入字符串上停止。

递归可枚举语言

如果 L 是某个 TM 接受的字符串集，则语言 L 是递归可枚举的。

如果 L 是递归可枚举语言，则 -

如果 w ∈ L 那么 TM 在最终状态中停止，

如果 w ∉ L 则 TM 在非最终状态中停止或永远循环。

如果 L 是递归语言，则 -

如果 w ∈ L 那么 TM 在最终状态中停止，

如果 w ∉ L 则 TM 停止在非最终状态。

递归语言也是递归可枚举的

证明 - 如果 L 是递归的，则有 TM 决定语言中的成员，然后 -

根据定义，M 可以识别这些字符串上接受的语言中的字符串。