[其他] 決定性(判定)問題的三種說法

[dharma (達)]

如果沒理解錯誤

決定性問題 = 判定問題

查英文是一樣的



下面有三個出處的詮釋

它們真的是指相同的事情嘛？

thank



1.維基：

在可計算性理論與計算複雜性理論中，所謂的決定性問題(Decision problem)是一個在某
些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定
性問題，此問題可回答是或否，且依據其x與y的值。




2.某書：(忘了哪本抄錄下來的)

p193 「判定問題」就是想找出一個嚴謹的逐步程序，藉由演繹邏輯的形式言自動做出證
明




3.好像是網路看到的：

不可判定問題是更加困難的
例如停機問題
它們無法在任何給定時間內解決

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.163.106.192
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1406593906.A.9BA.html
→ recorriendo :1是decision problem:簡單來說就是是非題
→ recorriendo :3是undecidable problem:的確可以翻譯成不可判定問題
→ recorriendo :不過undecidable的定義是針對圖靈機 意思是"沒有圖靈
→ recorriendo :機可以回答的是非題"
→ recorriendo :2是automated theorem proving的定義吧???
感謝
※ 編輯: dharma (118.163.106.192), 08/07/2014 11:34:30