Re: [問題] 決定性(判定)問題的三種說法
※ 引述《dharma (達)》之銘言：
: 如果沒理解錯誤
: 決定性問題 = 判定問題
: 查英文是一樣的
No, 你把一些事情混在一起了
你前面說的決定性問題,判定問題我猜是 decision problem
但是你後面的東西是在問 decidable problem ( "可判定性" )
: 下面有三個出處的詮釋
: 它們真的是指相同的事情嘛？
: thank
: 1.維基：
: 在可計算性理論與計算複雜性理論中，所謂的決定性問題(Decision problem)是一個在某
: 些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定
: 性問題，此問題可回答是或否，且依據其x與y的值。
yes, 這是 decision problem 的定義
: 2.某書：(忘了哪本抄錄下來的)
: p193 「判定問題」就是想找出一個嚴謹的逐步程序，藉由演繹邏輯的形式言自動做出證
: 明
這邊我看不懂, 個人猜測他是想說 "一個問題是可判定的代表有一個嚴謹的逐步程序.."
（不過我真的看不太懂, 這段理解可能也是全錯）
: 3.好像是網路看到的：
: 不可判定問題是更加困難的
: 例如停機問題
: 它們無法在任何給定時間內解決
(i) "停機問題" 是一個 "判定問題" (decision problem)
他說的是, 任意給你一個程式以及該程式的輸入, 請問用這個輸入執行該程式,
他是否會在有限時間內終止計算?
(ii) "停機問題" 是 "不可判定的" (undecidable)
對於停機問題這個判定問題, 不存在任何能回答停機問題的程式
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.142
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1406608614.A.8E2.html
推
07/29 19:57, , 1F
07/29 19:57, 1F
喔!!你說的這個才是對的
※ 編輯: suhorng (36.229.107.4), 07/29/2014 21:43:56
推
07/30 08:12, , 2F
07/30 08:12, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：