可判定性

维基百科，自由的百科全书
跳转至： 导航、 搜索

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

參考 [编辑]

E-to-the-i-pi.svg  這是與数学相關的小作品。你可以通过编辑或修订扩充其内容。
来自“http://zh.wikipedia.org/w/index.php?title=可判定性&oldid=26206152”