可判定性
(重定向自不可判定)
此条目没有列出任何参考或来源。 (2019年6月10日) |
此条目可参照英语维基百科相应条目来扩充。 |
语言的可判定性
编辑一个语言 ,是一个集合,且其补集为 。
当 是图灵机可识别时,语言 则称为半可判定。
当语言 不是图灵机可识别,则为不可判定语言。
当且仅当 和 都是图灵机可识别的时候,L才能称为可判定语言。
一般意义上的可判定性
编辑指一个询问真 / 假的问题是否可被回答。若不论一个问题答案为真或为假时均能得出该答案,则称这个问题、或解决该问题时所用的算法为可判定的;若只能在答案为真时得出、但在答案为假时不能做出判断,那么称为半可判定的;若根本不能得出为真或为假的结论,那么称为不可判定的。
参考
编辑这是一篇关于数学的小作品。您可以通过编辑或修订扩充其内容。 |