可判定性

维基百科,自由的百科全书
跳转至: 导航搜索

可判定性:一个语言L,是一个集合,且其补集\bar{L}
L图灵机可识别时,语言L则称为半可判定。
当语言L不是图灵机可识别,则为不可判定语言。
当且仅当L\bar{L}都是图灵机可识别的时候,L才能称为可判定语言。

參考[编辑]