停机问题
Halting问题是计算机科学中的一个问题。这个问题就是看一个计算机程序，找出这个程序是否会永远运行。如果一个程序能看任何其他程序，并能判断出其他程序是否会永远运行，我们就说它"解决了停顿问题"。
例如，这样的程序。
而True：继续。将永远循环，但程序
而False：继续。迅速停止。
有没有一种程序可以解决停顿问题？事实证明是没有的。我们证明了这个事实，如果有一个程序可以解决停顿问题，那么不可能的事情就会发生。所以，目前我们将表现得像真的有一个解决停顿问题的程序。这里，P是一个函数，它将评估函数F（用参数I调用），如果它永远运行，则返回true，否则返回false。
def P(F, I): 如果F(I)永远运行： 返回True； 否则： 返回False。P可以查看任何程序，并找出它是否会永远运行。我们用P制作一个新的程序，我们称之为Q，Q所做的就是看另一个程序，然后回答下面的问题："如果我们运行这个程序，让它看自己的副本，它是否会永远运行？"。"如果我们运行这个程序，让它看自己的副本，它会永远运行吗？"。我们之所以能制作Q，是因为我们有P，我们需要做的就是告诉Q，让它创建一个新的程序，这个新程序就是老程序看自己，然后用P来找出新程序是否永远运行。
def Q(F): return P(F, F);现在我们再做一个程序R，R看另一个程序，并询问Q对该程序的回答。如果Q回答"是的，如果我们运行这个程序并让它看自己的副本，它将永远运行"，那么R就停止。如果Q回答"不，如果我们运行这个程序并让它看自己的副本，它就不会永远运行"，那么R就进入一个无限循环，永远运行。
def R(F): if Q(F): return; //terminate else: while True: continue; //永远循环。现在我们看看如果让R看自己的副本会发生什么。有两种情况会发生：要么停止，要么永远运行。
如果运行R，让它看自己的副本，不会永远运行，那么Q回答"是的，如果我们运行这个程序，让它看自己的副本，就会永远运行"。但Q是在看R本身的时候说的。所以Q实际说的是："是的，如果我们运行R并让它看自己的副本，它将永远运行"。所以。如果R运行在它自己的副本上，不会永远运行，那么它就会永远运行。这是不可能的。
如果运行R，让它看自己的副本就会永远运行，那么Q回答说"不会，如果我们运行这个程序，让它看自己的副本就不会永远运行"。但Q是在看R本身的时候说的。所以Q实际说的是："不，如果我们运行R，让它看自己的副本，它不会永远运行"。所以。如果R运行在自己的副本上就会永远运行，那么它就不会永远运行。这也是不可能的。
无论发生什么，我们都会遇到不可能的情况。我们做错了什么，我们需要找出它是什么。我们做的大部分事情都没有错。我们不能说"让一个程序看自己的副本是错的"，也不能说"看另一个程序说了什么，如果它说了一件事就进入循环，如果它说了另一件事就停止"是错的。如果说我们不允许做这些事情，那是没有意义的。我们所做的唯一一件看起来可能是错误的事情，就是我们一开始就假装有P这样的程序存在。既然这是唯一可能出错的事情，一定有什么地方出错了，那就是这个。这就证明了P这样的程序是不存在的。不存在解决停顿问题的程序。
这个证明是艾伦-图灵在1936年发现的。
问题和答案
问：什么是Halting问题？答：Halting问题是计算机科学中的一个问题，它着眼于一个计算机程序，确定该程序是否会永远运行。
问：我们如何知道一个程序是否解决了停顿问题？
答：我们说一个程序 "解决了停顿问题"，如果它能观察任何其他程序并判断该其他程序是否会永远运行。
问：是否有办法证明没有这样的程序存在？
答：是的，通过证明如果有这样的程序，就会发生一些不可能的事情。这个证明是由艾伦-图灵在1936年发现的。
问：P是做什么的？
答：P是一个函数，它评估另一个函数F（用参数I调用），如果它永远运行则返回真，否则返回假。
问：Q是做什么的？
答：Q查看另一个程序，然后回答在自己身上运行这个相同的程序是否会导致无限循环的问题。它通过使用P对给定的函数F进行评估来做到这一点。
问：R是做什么的？
答：R查看另一个程序，并向Q询问它对该特定程序的答案。如果Q回答 "是的，如果我们运行这个程序并让它看它自己的副本，它将永远运行"，那么R就会停止；然而，如果Q回答 "不，如果我们运行这个程序并让它看它自己的副本，它不会永远运行"，那么R就会进入一个无限循环并永远运行。
问：当你让R看自己时会发生什么？
答：有两种情况会发生--要么R停止，要么永远运行--但根据已经证明的P等程序不存在的情况，这两种结果都是不可能的，所以在导致让R看自己的过程中，一定有什么地方出了问题。
