※ 引述《dharma (達)》之銘言：
: 如果沒理解錯誤
: 決定性問題 = 判定問題
: 查英文是一樣的
: 下面有三個出處的詮釋
: 它們真的是指相同的事情嘛？
: thank
: 1.維基：
: 在可計算性理論與計算複雜性理論中，所謂的決定性問題(Decision problem)是一個在某
: 些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定
: 性問題，此問題可回答是或否，且依據其x與y的值。
: 2.某書：(忘了哪本抄錄下來的)
: p193 「判定問題」就是想找出一個嚴謹的逐步程序，藉由演繹邏輯的形式言自動做出證
: 明
: 3.好像是網路看到的：
: 不可判定問題是更加困難的
: 例如停機問題
: 它們無法在任何給定時間內解決
你問的應該是計算理論方面的 turing-decidible 的問題吧
首先要wiki一下turing machine的定義
然後會知道turing machine執行最後會發生3個狀態
1.accept 2.reject 3.loop
因此可以把問題的難度分類
turing-decidible的問題是指
存在一turing machine
使其input是答案的就accept 不是答案的就reject 不管怎樣不會loop
舉個例子
問題為 檢查input是否是n個0與n個1的字串
000111 ac, 0000011111 ac, 0101 reject ...
我們可以設計一turing mechine確實可以檢查出這件事
而且不管input是什麼都不會掉進loop
(建造這個 並不是太簡單 也不是太難
通常計算理論課會放在習題 或是老師以此當範例說明)
所以這個問題就是turing-decidible
但有些問題是turing-undecidible
也就是不存在turing mechine 符合
"input是答案的就accept 不是答案的就reject 不管怎樣不會loop"
這條件
像停機問題就是turing-undecidible