第六百七十七章 停機(jī)問題（邏輯學(xué)）

　　圖靈一開始假設(shè)，有可能制造出一臺圖靈機(jī)，它可以計(jì)算出一個(gè)程序在給定某種輸入后是否會停止或永遠(yuǎn)運(yùn)行。然后他證明，這臺機(jī)器會導(dǎo)致一個(gè)矛盾，所以不可能存在。

　　圖靈提到的這個(gè)想法，后來被稱為停機(jī)問題。今天的軟件開發(fā)人員將其稱為無限循環(huán)，這是他們在編寫循環(huán)或遞歸函數(shù)時(shí)遇到的一個(gè)問題。

　　戴維斯在想什么是可以計(jì)算的，只要把不可以計(jì)算的全部排除，剩下的就是全部可以計(jì)算的了。

　　停機(jī)問題就是判斷任意一個(gè)程序是否能在有限的時(shí)間之內(nèi)結(jié)束運(yùn)行的問題。

　　該問題等價(jià)于如下的判定問題：是否存在一個(gè)程序P，對于任意輸入的程序w，能夠判斷w會在有限時(shí)間內(nèi)結(jié)束或者死循環(huán)。

　　最后戴維斯說：“存在一種圖靈機(jī)，其停機(jī)問題是遞歸無解的?！?p>　　停機(jī)問題就是判斷任意一個(gè)程序是否會在有限的時(shí)間之內(nèi)結(jié)束運(yùn)行的問題。如果這個(gè)問題可以在有限的時(shí)間之內(nèi)解決，則有一個(gè)程序判斷其本身是否會停機(jī)并做出相反的行為，這時(shí)候顯然不管停機(jī)問題的結(jié)果是什么都不會符合要求。所以這是一個(gè)不可解的問題。

　　停機(jī)問題本質(zhì)是一高階邏輯的不自恰性和不完備性。類似的命題有理發(fā)師悖論、全能悖論等。