# 停机问题

By [icona](https://paragraph.com/@happycity) · 2021-11-16

---

### 理发师悖论

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

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

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

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

这就是理发师悖论

### 停机问题

停机问题是指对给定任意的一个函数`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：这么厉害？那你判断停机我就无限循环，不停机我就返回，那你说我是停机还是不停机？

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

---

*Originally published on [icona](https://paragraph.com/@happycity/sQD5SSCK7b7KLJrsFRib)*