※ 引述《dharma (達)》之銘言： : 演算法之道裡寫道： : ...無法判定程式終結，這個結論對程式設計來說意義重大。就是這個緣故，程式永遠不 : 會是全自動的，即不可能由程式自己來寫程式、啟動程式、控制程式。也就是說，像「駭 : 客任務」那樣的情景永遠也不會出現。而隱含的意義是程式設計永遠也離不開程式設計師 : 。... : 書上這個論點 : 是現在學術和產業界的共識嗎？ : 是不是只有人類開發出仿生腦 : 才會有真正的人工智慧 : thank 停機問題（halting problem）是計算理論中最基本的常識。 首先，理論上我們簡單將程式分類成 1. 若存在某個演算法，對給定的問題如果有解， 可以在有限時間內給出答案，稱為「可計算」 computable (或是 semi-decidable） 2. 另一方面，不只是有解的情況，若是沒有解也可以在有限時間內回答， 則稱為「可判定」 decidable。 而 halting problem 的問題是：給定任意程式 P ，斷定它是否會停止。 很明顯的這是可計算的問題，因為只要去執行 P ， 若 P 在有限時間內結束，可以 P 在有限時間內得到答案。 但這個解法並不能在有限時間內推斷 P 「不會」結束。 （這邊提到的程式並不包含有輸入的程式。） 以上這個解法不成功，那是否存在另一個程式可以做到呢？也不行。 很久以前就已經有數學證明，不存在這樣的程式或機器。 原文接下來的推論，我認為是過於粗糙簡略了，按下不表。 不過呢，halting problem 討論的是「所有可能的程式」， 但可以把問題縮小到一些比較簡單能夠判定程式， 有些程式語言甚至保證所有的程式都會終止，像是 Agda 或是理論上的語言 polymorphic lambda calculus。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.4.165 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/Programming/M.1403603605.A.E4A.html