[問題] 決定性(判定)問題的三種說法
如果沒理解錯誤
決定性問題 = 判定問題
查英文是一樣的
下面有三個出處的詮釋
它們真的是指相同的事情嘛？
thank
1.維基：
在可計算性理論與計算複雜性理論中，所謂的決定性問題(Decision problem)是一個在某
些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定
性問題，此問題可回答是或否，且依據其x與y的值。
2.某書：(忘了哪本抄錄下來的)
p193 「判定問題」就是想找出一個嚴謹的逐步程序，藉由演繹邏輯的形式言自動做出證
明
3.好像是網路看到的：
不可判定問題是更加困難的
例如停機問題
它們無法在任何給定時間內解決
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.163.106.192
※ 文章網址: http://www.ptt.cc/bbs/Programming/M.1406594375.A.6AA.html
推
07/31 13:15, , 1F
07/31 13:15, 1F
→
07/31 13:15, , 2F
07/31 13:15, 2F
推
07/31 13:16, , 3F
07/31 13:16, 3F
→
07/31 13:17, , 4F
07/31 13:17, 4F
→
07/31 13:18, , 5F
07/31 13:18, 5F
→
07/31 13:18, , 6F
07/31 13:18, 6F
→
07/31 13:19, , 7F
07/31 13:19, 7F
→
07/31 13:20, , 8F
07/31 13:20, 8F
→
07/31 13:20, , 9F
07/31 13:20, 9F
→
07/31 13:21, , 10F
07/31 13:21, 10F
→
07/31 13:22, , 11F
07/31 13:22, 11F
→
07/31 13:24, , 12F
07/31 13:24, 12F
→
07/31 13:34, , 13F
07/31 13:34, 13F
→
07/31 13:34, , 14F
07/31 13:34, 14F
→
07/31 13:34, , 15F
07/31 13:34, 15F
→
07/31 13:35, , 16F
07/31 13:35, 16F
→
07/31 13:36, , 17F
07/31 13:36, 17F
→
07/31 13:36, , 18F
07/31 13:36, 18F
→
07/31 13:42, , 19F
07/31 13:42, 19F
→
07/31 13:42, , 20F
07/31 13:42, 20F
→
07/31 13:44, , 21F
07/31 13:44, 21F
→
07/31 13:44, , 22F
07/31 13:44, 22F
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
