可判定性问题

可判定性问题（德语：Entscheidungsproblem，意为“决策问题”）是数学和计算机科学中的一个基本问题，由德国数学家大卫·希尔伯特]和威廉·阿克曼于1928年提出。此问题为是否存在一个通用的方法，能在有限步骤内，判定一个数学命题的真假。^[1]

语言的可判定性

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

一般意义上的可判定性

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

参考

• 递归集合
• 假死机