# 停机问题

**Published by:** [icona](https://paragraph.com/@happycity/)
**Published on:** 2021-11-16
**URL:** https://paragraph.com/@happycity/sQD5SSCK7b7KLJrsFRib

## Content

理发师悖论 克里克岛的一座小城里有位理发师, 有一天他做出一项规定: 他只帮那些不给自己理发的人理发. 理发师的这个规定似乎很有道理, 既然有人自己给自己理发了, 那么我就不用"多此一举", 我再给这个人理发。 最初, 这个规定并没什么问题, 后来, 随着这个理发师自己的头发越来越长, 他发现他陷入了一个两难的境地: 他该不该给自己理发? 如果他不给自己理发，那按照规定，他应该给自己理发 如果他给自己理发，那按照规定，他不能给自己理发 这就是理发师悖论 停机问题 停机问题是指对给定任意的一个函数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：这么厉害？那你判断停机我就无限循环，不停机我就返回，那你说我是停机还是不停机？ 所以不存在这样的程序来解决停机问题

## Publication Information

- [icona](https://paragraph.com/@happycity/): Publication homepage
- [All Posts](https://paragraph.com/@happycity/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@happycity): Subscribe to updates
- [Twitter](https://twitter.com/caishaowu1): Follow on Twitter