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

[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/Programming/M.1406594375.A.6AA.html
推 longlongint:某書是什麼書？ 當然是看該領域自己
→ longlongint:給的定義呀
推 longlongint:一般Decision翻譯成"決策"
→ longlongint:deterministic翻譯成確定性(的)
→ longlongint:原PO的1應該來自於 人工智慧領域
→ longlongint:2是應該是從 哲學或邏輯學 來的
→ longlongint:要不然又是AI裡面的自動理論推導機
→ longlongint:3是演算法或計算機理論的問題
→ longlongint:更正 計算理論
→ longlongint:恩... 查了一下WIKI發現自己記憶力不
→ longlongint:好  樓主抱歉
→ longlongint:看WIKI吧http://ppt.cc/xBBX
→ longlongint:不專業的說法 "可決定"的意思為
→ longlongint:"可以算出答案、可計算、可以回答"
→ longlongint:反之則是"不可計算、算不出答案、不
→ longlongint:能回答"
→ longlongint:我自己搞錯的deterministic則是
→ longlongint:類似"每一步都明確地知道該如何行動"
→ Killercat:不可決定的意思其實是...
→ Killercat:無法確定能再給定時間內得到答案 :P
→ Killercat:除非有數學證明任意解都有最短循環
→ Killercat:比方說有名的3n+1問題