停机问题

克里克岛的一座小城里有位理发师, 有一天他做出一项规定: 他只帮那些不给自己理发的人理发. 理发师的这个规定似乎很有道理, 既然有人自己给自己理发了, 那么我就不用"多此一举", 我再给这个人理发。

最初, 这个规定并没什么问题, 后来, 随着这个理发师自己的头发越来越长, 他发现他陷入了一个两难的境地: 他该不该给自己理发?

如果他不给自己理发，那按照规定，他应该给自己理发

如果他给自己理发，那按照规定，他不能给自己理发

这就是理发师悖论

停机问题是指对给定任意的一个函数f和输入t, 判断f对t是否会永远运行下去; 如果程序的运行时间是有限长的, 我们称f对t停机.

假设存在一个函数isStop(Object program,Object input)，它可以判断程序是否停机。

那么我们构造这样一个函数，假设 Object A 是函数 modifyStop

void modifyStop(Object A) {
  if(isStop(A,A)) {
    while(true);
  }else {
    return;
  }
}

如果 modifyStop 对 A 停机，说明 isStop(A,A) 返回 false，isStop(A,A) 返回 false，说明 modifyStop 对 A 不停机

如果 modifyStop 对 A 不停机，说明 isStop(A,A) 返回 true，isStop(A,A) 返回 true，说明 modifyStop 对 A 停机

通俗来说，就是

程序A：我可以判断所有程序是否停机

程序B：这么厉害？那你判断停机我就无限循环，不停机我就返回，那你说我是停机还是不停机？

所以不存在这样的程序来解决停机问题

icona