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

在学习计算理论(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决定语言中的成员，然后-