可判定性

此條目没有列出任何参考或来源。 (2019年6月10日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。

此條目可参照英語維基百科相應條目来扩充。 若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。

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

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

• 递归集合
• 假死機

这是一篇关于数学的小作品。您可以通过编辑或修订扩充其内容。 查 论 编