可判定性

語言的可判定性

一個語言$L$，是一個集合，且其補集為${\overline {L}}$ 。
當$L$是圖靈機可識別時，語言$L$則稱為半可判定。
當語言$L$不是圖靈機可識別，則為不可判定語言。
當且僅當$L$和${\bar {L}}$都是圖靈機可識別的時候，L才能稱為可判定語言。

一般意義上的可判定性

指一個詢問真 / 假的問題是否可被回答。若不論一個問題答案為真或為假時均能得出該答案，則稱這個問題、或解決該問題時所用的算法為可判定的；若只能在答案為真時得出、但在答案為假時不能做出判斷，那麼稱為半可判定的；若根本不能得出為真或為假的結論，那麼稱為不可判定的。

參考

• 遞歸集合
• 假死機