Re: [請益] 無法判定程式終結

[xiaoa (不事生產)]

我也不懂, 不過可以討論看看
※ 引述《dharma (達)》之銘言：
: 演算法之道裡寫道：
: ...無法判定程式終結，這個結論對程式設計來說意義重大。就是這個緣故，程式永遠不
: 會是全自動的，即不可能由程式自己來寫程式、啟動程式、控制程式。也就是說，像「駭
: 客任務」那樣的情景永遠也不會出現。而隱含的意義是程式設計永遠也離不開程式設計師
: 。...
所謂"無法判定程式終結"是什麼意思?
我知道的只有連皮毛都稱不上的東西
無法判定程式終結 是說運算中有逃不出來的loop, 這樣嗎?

我想到像OS, 或一些介面(offices, browsers等)
它們算程式嗎?
我們不動它時, 它在"執行"什麼?
如果沒有在執行什麼, 它為什麼不會結束(關掉)?

要釐清上述問題, 才能進一步討論
: 書上這個論點
: 是現在學術和產業界的共識嗎？
: 是不是只有人類開發出仿生腦
: 才會有真正的人工智慧
: thank

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.9.101.18
※ 文章網址: http://www.ptt.cc/bbs/ask-why/M.1402173067.A.93C.html
→ kougousei:無法判定程設終結就是計算理論裡面的halting problem...
所以我的方向算是對了
因為在OS底下, 部分無法自行終結的程式, 可以人為的終結
說明程式雖無法自行終結, 使用者卻可以強迫終結

雖然程式對自身或另一個程式判定終結/無法終結, 是邏輯上循環矛盾的
但對人來說, 要做這種判斷, 情況也是一樣的(只不過人類對檢測出"循環"的直覺比較強)
我們常常也無法預期程式是否能自行終結
人類判斷的方式, 更多時候不是由邏輯運算出發, 而是靠經驗預期去判斷

如果你寫一個程式, 讓它處理某個問題
它運轉了3分鐘沒停, 而你預期這項工作只要花20秒
你就會認為程式可能有問題了
但如果你本來就預期程式要跑24個小時才能結束
你不會在程式跑了25個小時後卻未結束, 就認定程式陷入回圈

所以我以為只要能寫出一個有類似這樣的功能的管理性程式
就能最低限度的, 對無法自行終結的程式, 進行強迫終結
但以上只保證跑程式不會當機
卻不能保證有個 自主程式 能編寫/修正出一套不會有停機問題的程式
因為判定程式終結可以簡化成用時間衡量
修正程式卻需要電腦對問題的理解
所以這裡又陷入另一個循環矛盾
因為電腦若打從開始就理解了問題, 它不應該寫出有問題的程式
我想, 這個問題也是不能用單純的邏輯運算來解套的, 需要參考人為解套的方式
※ 編輯: xiaoa (203.106.157.101), 06/08/2014 14:44:17
→ sitos:你的方向不太正確， halting problem 要揭示的是程式的極限
→ sitos:重點是 Turing machine 的計算模型裡面，某些問題沒辦法解
→ sitos:也就是 undecidable 的概念， halting problem 只是一個例子
→ sitos:重點其實並不在於判斷特定的程式和輸入到底會不會停下來
→ sitos:等睡飽頭又不痛的時候再來完整回覆一下這個議題好了
→ xiaoa:halting problem是邏輯的問題. 所以我的看法是, 用單純的邏
→ xiaoa:輯運算, halting problem是無解的
→ xiaoa:難得見sitos發言, 坐等回文~
→ WINDHEAD:不能被計算證明不代表不能被證明
→ xiaoa:說好的回覆呢 T_T