可判定性問題

可判定性問題（德語：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]