可判定性問題

可判定性問題（德語：Entscheidungsproblem，意為「決策問題」）是數學和計算機科學中的一個基本問題，由德國數學家大衛·希爾伯特]和威廉·阿克曼於1928年提出。此問題為是否存在一個通用的方法，能在有限步驟內，判定一個數學命題的真假。^[1]

语言的可判定性

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

一般意义上的可判定性

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

參考

參考文獻

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

^ David Hilbert and Wilhelm Ackermann. Grundzüge der Theoretischen Logik. Springer, Berlin, Germany, 1928. English translation: David Hilbert and Wilhelm Ackermann. Principles of Mathematical Logic. AMS Chelsea Publishing, Providence, Rhode Island, USA, 1950

[1] David Hilbert and Wilhelm Ackermann. Grundzüge der Theoretischen Logik. Springer, Berlin, Germany, 1928. English translation: David Hilbert and Wilhelm Ackermann. Principles of Mathematical Logic. AMS Chelsea Publishing, Providence, Rhode Island, USA, 1950

[1]