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年发现的。