Re: [請益] 無法判定程式終結
終於覺得自己比較有時間可以回文了。 :)
首先 halting problem 是什麼，我就不贅述了，因為我不想要把課本一整章抄上來，
而且我也沒自信把問題的描述簡化以後，原本不懂的人還看得懂，這樣的簡化沒意義。
為了要保持描述的流暢性，下面寫的可能會把幾個相似但不同的概念混用，
專有名詞的使用上面可能會比較不精確，有興趣的人可以再查書來分別這些名詞。
簡單來說， Turing 那個時代的數學家們在思考的問題是「計算」到底是什麼。
這當然是一個定義問題，當時 Turing 試著對「計算」作定義，他的定義是，
他設計了一個假想的「計算模型」，也就是廣為人知的 Turing machine ，
然後他定義 Turing machine 的運算過程就是「計算」。在有了定義以後，
下一個要問的問題當然是，那 Turing machine 到底「多能算」，也就是說，
Turing machine 能夠解決的問題到底包含哪些範圍。
Turing machine 雖然是一個假想的計算模型，但它其實非常強大。一般的問題難不倒它，
因此 Turing 為了證明 Turing machine 也有它的極限，特意去找算不出來的問題，
這邊所謂的算不出來，或說無法回答，或說 undecidable ，就是沒有任何一個演算法，
可以在任意給定一組輸入值的情況下，決定這個問題是 Yes 還是 No 。
而 Turing 找的問題就是 halting problem ，這個問題的輸入是「任意一個程式」加上
「該程式的任意一組輸入值」，而要回答的問題是這個程式搭配這個輸入值會不會停。
略過證明過程，總之 Turing 證明了不可能設計出一套演算法來解決這個問題。
因為 halting problem 是要問 Turing machine 的計算極限，而不是問人的極限，
所以在考慮 halting problem 的時候，去問人能不能用直覺去判斷云云，
基本上不是 halting problem 的重點。而且就算使用者可以強迫程式終止，
但 halting problem 要能解，必須要是「任意輸入值」該演算法都能回答，
當然也就包括「使用者不強迫終止」的這種輸入狀態。只要有一個 case 不能解，
那麼整個 halting problem 就是不能解。當然靠經驗去預估計算時間，
超過預估的時間就終止等等，這也都沒回答到問題，因為 halting problem 要問的，
不是「這個程式應不應該會停」，而是「這個程式在這組輸入下會不會停」。
Turing 等人所關心的問題，其實根本不是特定的程式會不會停，
當然他們也不在意真的掉到無窮迴圈的時候應該要怎麼跳出來，
也不那麼在意怎麼樣寫程式才不會掉到無窮迴圈裡面。
另外要補充的是，事實上我們現在所使用的電腦，都不滿足 Turing machine 的需求。
因為 Turing machine 假設具有無限長的 Tape ，或說無限大的記憶體。
但現在的電腦的記憶體都是有限的。
所以雖然沒有一個演算法可以判斷：
「一個程式搭配一組輸入值在 Turing machine 執行會不會停？」
但是其實存在一個演算法可以判斷：
「一個程式搭配一組輸入值在記憶體有限的電腦上執行會不會停？」
所以回到 dharma 板友一開始問的問題，演算法之道所寫的到底對不對。
其實我不知道，因為如果我們不把 halting problem 擺在 Turing machine 上問，
而是把 halting problem 擺在一個給定記憶體大小的電腦上來問，
那其實我們可以判定程式會不會終結。但即使如此，程式就能全自動嗎？我不知道。
而反過來說，雖然強如 Turing machine 的機器都有它的極限，
無法回答所有的問題。但「人」同樣也有自身的極限，也有很多問題不能回答。
似乎也沒有理由說明不能解 halting problem ，就不可能程式自己來寫程式，
或是不可能像駭客任務那樣，或者程式設計永遠離不開程式設計師。
--
活著的目的是為主活 然後為主死
死亡的目的是為主死 然後為主活
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.213.10
※ 文章網址: https://www.ptt.cc/bbs/ask-why/M.1425304225.A.882.html
→
03/09 09:53, , 1F
03/09 09:53, 1F
推
03/23 23:42, , 2F
03/23 23:42, 2F
討論串 (同標題文章)