Re: [問題] 無法判定程式終結

看板Programming作者xcycl (XOO)時間11年前 (2014/06/24 17:53)推噓3(3推 0噓 15→)

留言18則, 4人參與討論串2/2 (看更多)

※ 引述《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://www.ptt.cc/bbs/Programming/M.1403603605.A.E4A.html

→

freef1y3

07/02 22:44, , 1^F

07/02 22:44, 1^F

→

freef1y3

07/02 22:46, , 2^F

07/02 22:46, 2^F

→

freef1y3

07/02 22:47, , 3^F

07/02 22:47, 3^F