什么是递归和递归可枚举语言？
在学习计算理论(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决定语言中的成员，然后-
如果x在语言L中，则M接受x。
如果x不在语言L中，则M拒绝x。
根据定义，M可以识别这些字符串上接受的语言中的字符串。