查看“︁可判定性”︁的源代码

{{unreferenced|time=2019-06-10T19:17:17+00:00}}
{{Request translation|en}}

==语言的可判定性==
一个语言<math>L</math>，是一个[[集合 (数学)|集合]]，且其[[补集]]为<math>\overline{L}</math> 。<br />
当<math>L</math>是[[图灵机]]可识别时，语言<math>L</math>则称为半可判定。<br />
当语言<math>L</math>不是图灵机可识别，则为不可判定语言。<br />
'''当且仅当<math>L</math>和<math>\bar{L}</math>都是图灵机可识别的时候，L才能称为可判定语言。'''

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

==參考==
* [[递归集合]]
*[[假死機]]

{{math-stub}}

[[Category:递归论]]
[[Category:戈特弗里德·萊布尼茨]]