语言的可判定性

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

一般意义上的可判定性

指一个询问真 / 假的问题是否可被回答。若不论一个问题答案为真或为假时均能得出该答案，则称这个问题、或解决该问题时所用的算法为可判定的；若只能在答案为真时得出、但在答案为假时不能做出判断，那么称为半可判定的；若根本不能得出为真或为假的结论，那么称为不可判定的。

参考

递归集合

假死机

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。