图灵可识别语言

图灵可识别语言又可被称为递归可枚举语言或递回可枚举语言。设 M 是一台图灵机，若在输入串 ω 上 M 运行后可进入接受状态并停机，则称 M 接受串 ω。M 所接受的所有字符串的集合称为 M 所识别的语言，简称 M 的语言，记作 L(M)。

设S是一个语言，若存在图灵机 M 使得 L(M) = S，则称图灵机 M 识别 S，且 S 称为图灵可识别语言。

一个语言是图灵可识别语言当且仅当它是递归可枚举语言。