※ 引述《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 ---------------------------------------------------------- 有個有趣的問題是 電腦上可否寫個程式 來 判斷任何程式 會停止或掉進無窮迴圈 這在一些書上或資料上 都只說因為停機問題是undecidible 所以不可能 這其實是不嚴謹的 應該更仔細思考 Turing-machine是一種抽象電腦 它的tape可以放進任意大的input 可以比宇宙中所有粒子數還大 而且state數量也沒限制 我們一般看到的停機問題的證明都是在此模型上證明的 但真實的電腦不是 它的tape是"有限的" state也是"有限的" 若問可解決的問題 turing-machine比真實的電腦威力還大 所以以真實的電腦為模型的停機問題應該要另外證明 這部份我就沒再深入研究了 一般書上或網路上直接那樣寫其實是邏輯上的錯誤 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.10.127 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/Programming/M.1407046172.A.F6C.html ※ 編輯: Arton0306 (220.137.10.127), 08/03/2014 14:42:14 你是指有限tape的turing machine因為configuration有限 所以這model下的停機問題是decidable嗎?? 我後來也有想到這是turing-decidable 只是要在無限tape版的去檢查有限tape版的 如果是在有限tape(長度n)的去檢查有限tape(長度n) 這應該不行 在tape長度短時連另一台machine的encode都放不下XD 狀態數我的意思跟你是一樣的 有點難表達XD 就|Q|沒有上限 ※ 編輯: Arton0306 (220.137.10.127), 08/03/2014 17:39:02 ※ 編輯: Arton0306 (220.137.10.127), 08/03/2014 17:53:16