图灵停机问题的史上最详细描述 -一个渣渣

图灵停机问题

停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。
等价于是否存在一个程序H，对于任意输入的程序P，能够判断P会在有限时间内结束或者死循环。

假设存在这样的一个函数H来判断一个程序P在输入为 I 情况下是否会停机。最后用反证法，证明不存在这样的H.
如果P停机，H输出0表示P是停机，否则H输出1表示P是死循环。

int H(P, I); // 这里的H函数有两种返回值，死循环(1) 或 停机(0)

程序本身也是一种数据，因此它可以作为输入（例如Pascal的编译器本身就可以用Pascal所写成，所以程序在自己身上运行自己也是合理的），故H应该可以判定当将P作为P的输入时，P是否会停机。
即：

int H(P, P); // 这里的H函数有两种返回值，死循环(1) 或 停机(0)

然后我们再定义一个过程U( P )，其流程如下：
U( P )调用H(P, P)：
如果H(P, P)进入死循环，U( P )就停机。
如果H(P, P)停机，U( P )就进入死循环。
也就是说，U( P )做的事情就是做出与H(P, P)的输出相反的动作。

int U(P)
{
    if (H(P,P) == 1){ // 如果H死循环
        return 0; // 此时U会停机
    }else{ // 否则
        while(1){} // 此时U会死循环
    }
}

暂时一切正常，但如果我们把P换成U呢？

int U(U)
{
    if (H(U, U) == 1){ // 如果H死循环
        return 0; // 此时U会停机
    }else{ // 否则
        while(1){} // 此时U会死循环
    }
}

出现问题了。H函数判断U在输入为U情况下是死循环时，U却会停机。而当H判断U是停机时，U却进入了死循环。矛盾了。H判断不准确了。所以不存在这么牛逼的程序H。
所以，不存在解决停机问题的通用算法。

理发师悖论：村子里有个理发师，这个理发师有条原则是，对于村子里所有人，当且仅当这个人不自己刮胡子，理发师就给这个人刮胡子。如果这个人自己刮胡子，理发师就不给这个人刮胡子。无法回答的问题是，理发师给自己刮胡子么？

转载自原文链接, 如需删除请联系管理员。