圖靈停機問題(The Halting Problem)——巧妙的證明

NO IMAGE

     轉自:  https://blog.csdn.net/niushuai666/article/details/7260957

     不存在這樣一個程式(演算法),它能夠計算任何程式(演算法)在給定輸入上是否會結束(停機)。

那麼,如何來證明這個停機問題呢?
反證!假設我們某一天真做出了這麼一個極度聰明的萬能演算法(就叫God_algo吧),你只要給它一段程式(二進位制描述),再給它這段程式的輸入,它就能告訴你這段程式在這個輸入上會不會結束(停機),我們來編寫一下我們的這個演算法吧:
bool God_algo(char* program, char* input)
{
    if(<program> halts on <input>)
        return true;
    return false;
}

這裡我們假設if的判斷語句裡面是你天才思考的結晶,它能夠像上帝一樣洞察一切程式的宿命。現在,我們從這個God_algo出發匯出一個新的演算法:
bool Satan_algo(char* program)
{
if( God_algo(program, program) )
{
       while(1);        // loop forever!
       return false;   // can never get here!
}
else
       return true;
}
正如它的名字所暗示的那樣,這個演算法便是一切邪惡的根源了。當我們把這個演算法運用到它自身身上時,會發生什麼呢?
Satan_algo(Satan_algo);
我們來分析一下這行簡單的呼叫:
顯然,Satan_algo(Satan_algo)這個呼叫要麼能夠執行結束返回(停機),要麼不能返回(loop forever)。
如果它能夠結束,那麼Santa_algo演算法裡面的那個if判斷就會成立(因為God_algo(Santa_algo,Santa_algo)將會返回true),從而程式便進入那個包含一個無窮迴圈while(1);的if分支,於是這個Satan_algo(Satan_algo)呼叫便永遠不會返回(結束)了。
如果不能結束(停機),則if判斷就會失敗,從而選擇另一個if分支並返回true,即Satan_algo(Satan_algo)又能夠返回(停機)。
總之,我們有:
Satan_algo(Satan_algo)能夠停機=> 它不能停機
Satan_algo(Satan_algo)不能停機=> 它能夠停機

所以它停也不是,不停也不是,左右矛盾。