递归可枚举语言

在数学、逻辑和计算机科学中，递归可枚举语言是也叫做部分可判定语言或图灵可识别语言的形式语言类型。它在形式语言的乔姆斯基层级中叫做类型-0语言。所有递归可枚举语言的类叫做RE。

形式定义

递归可枚举语言定义：设S ⊆ Σ*为一个语言，E是一个枚举器，若L（E） = S，则称E 枚举了语言S。若存在这样
的E，S就称为递归可枚举语言。
注意，枚举器E可以以任意的顺序枚举语言L（E），而且L（E） 
中的某个串可能会被E多次重复地打印。
图灵可识别语言定义：设是一台图灵机，若在输入串上运行后可进入接受状态并停机，则称接受串。所接受的所有字符串的集合称为所识别的语言，简称的语言，记作。 
设是一个语言，若存在图灵机使得，则称图灵机 识别，且称为图灵可识别语言。

图灵可识别语言与图灵可判定语言的关系

注意图灵可识别语言和图灵可判定语言的区别：若是图灵可识别语言，则只需存在一台图灵机，当的输入时，一定会停机并进入接受状态；当的输入时，可能停机并进入拒绝状态，或者永不停机。而若是图灵可判定语言，则必须存在图灵机，使得对于任意输入串，总能停机，并根据  属于或不属于分别进入接受或拒绝状态。
并不是所有的语言都是图灵可识别的，可以证明存在图灵不可识别语言。