停机问题(英语:halting problem)是逻辑数学中可计算性理论的一个问题。通俗地说,停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题:是否存在一个程序P,对于任意输入的程序w,能够判断w会在有限时间内结束或者死循环。

时间:2021-07-17 10:31:18

htps://baike.baidu.com/item/停机问题/4131067?fr=aladdin

理发师悖论:村子里有个理发师,这个理发师有条原则是,对于村里所有人,当且仅当这个人不自己理发,理发师就给这个人理发。如果这个人自己理发,理发师就不给这个人理发。无法回答的问题是,理发师给自己理发么?
停机测试悖论:计算机里有个测试程序,这个测试程序的原则是,对于计算机里所有程序,当且仅当这个程序不递归调用自己(输出停机),测试程序就调用它(对应不停机)。如果这个程序递归调用自己(对应不停机),测试程序就不调用它(对应停机)。无法回答的问题是,测试程序递归调用自己么?