什么是停止问题？

每当人们询问关于编程的停止问题时，人们都会回答：“如果你只是添加一个循环，你就停止了程序，因此你不能自动执行任务 ”

说得通。如果你的程序有一个无限循环，那么当你的程序运行时，你无法知道程序是否仍然在处理input，或者只是循环无限。

但是，这似乎有些违反直觉。如果我正在编写一个暂停问题解决器，它将源代码作为input。 rascher@localhost$ ./haltingSolver source.c

如果我的代码（source.c）如下所示：

 for (;;) { /* infinite loop */ }

看来我的程序看起来很容易。如果条件只是基于文字而没有variables，那么你总是知道循环的结果，如果有variables（例如while（x <10）），看看是否有variables那些variables都会被修改，如果没有，那么你总是知道循环的结果。

当然，这些检查不是微不足道的（计算指针算术等），但似乎不可能。例如：

 int x = 0 while (x < 10) {}

可以被检测到。以及 – 虽然不平凡：

 int x = 0 while (x < 10) { x++; if (x == 10) { x = 0 } }

现在用户input怎么样？那就是踢球，那是什么让一个程序变得不可预测。

 int x = 0; while (x < 10) { scanf("%d", &x); /* ignoring infinite scanf loop oddities */ }

现在我的程序可以这样说：“如果用户input一个10或者更大的值，那么程序将会暂停，而在所有其他的input中，它将会再次循环。

这意味着，即使有数百个input，也应该能够列出程序停止的条件。事实上，当我编写一个程序时，我总是确保有人有能力终止它！我并不是说所产生的条件清单是微不足道的 ，但对我来说似乎并不可能。你可以从用户那里得到input，用它们来计算指针索引等等，但是这只是增加了一些条件来确保程序将会终止，并不能够枚举它们。

那么停滞的问题究竟是什么？我不知道我们不能写出一个问题来检测无限循环？或者，为什么“循环”这样一个经常引用的例子呢？

UPDATE

所以，让我稍微改变一下问题： 适用于计算机的暂停问题是什么？ 然后我会回应一些评论：

很多人都说这个程序必须能够处理“任意的input”。但是在电脑上，从来没有任何的任意input。如果我只input一个字节的数据，比我只有2 ^ 8个可能的input。所以，举个例子：

 int c = getchar() switch (c) { case 'q': /* quit the program */ }

突然之间，我已经把所有的可能性都考虑在内了。如果c具有位模式0x71，则它执行一件事。对于所有其他模式，它做了别的事情。甚至一个接受任意stringinput的程序也不是真正的“任意的”，因为资源是有限的，这意味着虽然适用“任意”的理论，但它并不完全是一对一的实践。

人们引用的另一个例子是这样的：

 while (n != 1) if (n & 1 == 1) n = 3 * n + 1; else n /= 2;

如果n是一个32位的整数…那么我可以直观地告诉你这是否会停止。

我想这个编辑不是问任何问题，但是我见过的最有说服力的例子是这样的：

假设你有你的魔法程序/方法来确定一个程序暂停。

 public bool DeterminesHalt(string filename, string[] args){ //runs whatever program you tell it do, passing any args //returns true if the program halts, false if it doesn't }

现在让我们说我们写一小段代码，如…

 public static void Main(string[] args){ string filename = Console.ReadLine(); //read in file to run from user if(DeterminesHalt(filename, args)) for(;;); else return; }

所以对于这个例子，我们可以编写一个程序来做与我们的魔法停止方法完全相反的程序。如果我们以某种方式确定一个给定的程序将停止，我们就跳入一个无限循环; 否则，如果我们确定程序处于无限循环，则结束程序。

再说一遍，如果你故意写一个包含无限循环的程序……“解决暂停问题”有点没有实际意义，不是吗？

编辑（比原来的答案晚得多）：良好math MarkCC，最近坏math用具体的例子写了一个关于停止问题的极好的讨论。

停止问题基本上是一个正式的方式，问你是否可以判断一个任意程序是否最终会停止。

换句话说，你可以编写一个叫halting oracle的程序，HaltingOracle（程序，input），如果程序（input）最终会停止，返回true，否则返回false。

答案是：不，你不能。

跟进关于停车问题的input是相关的还是红鲱鱼的问题：是的，input是重要的。 另外，似乎有一些混乱，我认为在“任意”更正确的地方使用“无限”。

实际的例子 ：假设你正在从事质量保证工作，你应该写一个暂停检查程序（又名oracle），以确认开发团队编写的任意程序（D）以及任何提供的任意input用户（I），当给定inputI时，程序D将最终停止。

Cue经理的声音 ：“浩浩，那些愚蠢的用户，让我们确保不pipe他们input什么垃圾，我们的服务器任务将永无止境地终结，这样吧，代码猴！

这似乎是个好主意，对吧？你不希望你的服务器挂起，对吧？

停止问题告诉你的是，你正在被交给一个无法解决的任务。相反，在这种情况下，您需要计划超过阈值时间的任务并准备好取消它们。

Mark使用代码而不是input来说明问题：

 def Deciever(i): oracle = i[0] in = i[1] if oracle(Deceiver, i): while True: continue else: return i

在我的评论讨论中，我走了恶意input操纵的路线，迫使一个无法解决的问题。马克的例子是更加优雅，使用停止甲骨文打败自己：

所以，Deceiver的input实际上是两个元素的列表：第一个是build议的暂停oracle。第二个是另一个input。甲骨文所要做的是：“你认为我会停止input吗？”。如果神谕说：“是的，你会停下来的”，然后程序进入无限循环。如果神谕说“不，你不会停止”，那么它会停下来。所以不pipe甲骨文说什么，都是错的。

换句话说，没有作弊，重新格式化input，可数/无数infinities或任何其他干扰，马克已经写了一段代码，可以击败任何停止甲骨文计划。你不能写一个答案来回答Deceiver是否永远停止的问题。

原始答案：

从伟大的维基百科：

在可计算性理论中，暂停问题是一个决策问题，可以表述如下：给定一个程序和一个有限input的描述，决定程序是否结束运行或者将永远运行，给定input。

Alan Turing在1936年certificate了解决所有可能的程序input对的暂停问题的一般algorithm是不存在的。我们说停止问题在图灵机上是不可判定的。 Copeland（2004）将实际的术语停止问题归因于Martin Davis。

其中一个关键点是你无法控制程序或input。你被交给了你，回答这个问题。

还要注意，图灵机是有效的可计算性模型的基础。换句话说，你用现代计算机语言所做的一切都可以映射回这些典型的图灵机。因此，停止问题在任何有用的现代语言中都是不可判定的。

为了解决暂停问题，你必须开发一种algorithm，以确定任意程序是否停止任意input ，而不仅仅是例子中相对简单的情况。

这是一个简单的解释certificate停止问题是不可判定的。

假设你有一个程序H，它计算一个程序是否停止。 H有两个参数，第一个是程序的描述，P，第二个是input，I.如果P停止inputI，则返回真，否则返回假。

现在编写一个程序p2，它将input另一个程序p3的描述。 p2调用H（p3，p3），如果H返回true，则循环，否则暂停。

当我们运行p2（p2）时会发生什么？

它必须同时循环和停止，导致宇宙爆炸。

这已经被击败得如此之好，以至于实际上有一个诗歌的证据，由Geoffrey Pullum（语言日志名人之一）的~~刘易斯·卡洛尔~~ （ ~~Lewis Carroll）~~博士的风格所写。

有趣的东西。这里有一个口味：

这是我将要使用的技巧 – 而且很简单。
我将定义一个程序，我将称之为Q，
这将使用P预测停止成功
激起一个可怕的逻辑混乱。

…

无论P如何performance，Q都会舀出：
Q使用P的输出使P看起来很愚蠢。
无论P说什么，都无法预测Q：
P是错的，错的时候是错的！

有一个确定的证据在维基百科的停机问题。

为了说明，为什么只是应用一些技术来循环是不够的，考虑下面的程序（伪代码）：

 int main() { //Unbounded length integer Number i = 3; while(true) { //example: GetUniquePositiveDivisiors(6) = [1, 2, 3], ...(5) = 1, ...(10) = 1, 2, 5, etc. Number[] divisiors = GetUniquePositiveDivisiors(i); Number sum = 0; foreach(Number divisor in divisiors) sum += divisor; if(sum == i) break; i+=2; } }

你能想到一个方法，如果这个代码暂停将返回true，否则为false？

慎重考虑。

如果偶然的情况下，你们正在争夺一枚菲尔兹奖牌，那么想象一下这些问题的一些代码代替了上述情况。

“如果你只是添加一个循环，你有停止计划，因此你不能自动化任务”

听起来就像是在推广暂停问题的应用一样。有很多特定的循环，你可以certificate终止。目前已经有研究可以对广泛的程序进行终止检查。例如，在Coq中，你仅限于可以certificate终止的程序。微软有一个名为“终结者”的研究项目，使用各种近似来certificate程序将终止。

但是，请记住，停止问题不仅仅是玩具的例子。这些解决了一般的“停止问题”，因为它们不适用于每个程序。

问题是暂停的问题说有些程序你无法知道它们是否会在没有运行的情况下终止，这意味着你可能永远不会做出决定是否停止。

一个可能或可能不会停止的例子（在Haskell中）：

 collatz 1 = () collatz !n | odd n = collatz (3 * n + 1) | otherwise = collatz (n `div` 2)

或者更容易访问的东西：

 while (n != 1) if (n & 1 == 1) n = 3 * n + 1; else n /= 2;

给定每个整数> = 1，这个程序会停止吗？那么，它到目前为止工作，但没有定论说，将停止每一个整数。我们猜测 Lothar Collatz可追溯到1937年，但没有证据。

在参考“人们回应”这一小节时，如果您只是添加一个循环，您就有了暂停程序，因此您不能自动执行任务“”，我将添加以下详细信息：

对于图灵机来说，那些不能通过algorithm计算任意程序是否会停止的post是绝对正确的。

事情是，并不是所有的程序都需要图灵机。这些程序可以用一个概念上的“较弱”的机器来计算 – 例如，正则expression式可以完全由一个有限状态机来实现，它总是停止input。这不是很好吗？

我打赌，当人们说“加一个循环”时，他们试图expression这样的观点，即当一个程序足够复杂的时候，它需要一个图灵机，因此应用了停机问题（作为一个想法）。

这可能与问题略有相关，但我相信，考虑到问题的细节，这是值得指出的。 🙂

图灵的一个很好的例子是自我指涉 – 假设有一个程序可以检查另一个程序，并确定它是否会停下来。将暂停程序检查程序ITSELF送入暂停程序检查程序 – 它应该怎么做？

这是一个暂停问题永远无法解决的程序。

假设你有你的魔法程序/方法来确定一个程序暂停。

 public bool DeterminesHalt(string filename, string[] args){ //runs whatever program you tell it do, passing any args //returns true if the program halts, false if it doesn't }

现在让我们说我们写一小段代码，如…

 public static void Main(string[] args){ string filename = Console.ReadLine(); //read in file to run from user if(DeterminesHalt(filename, args)) for(;;); else return; }

无论您进行了多less次input检查，都没有可能的解决scheme来确定每个程序是否被写入停止。

到目前为止，有很多有趣的具体的例子/类比。如果您想更深入地阅读背景知识，Charles Petzold在图灵的原创论文“注解图灵” （ The Annotated Turing）上有一本很好的书。

在一个相关的，侧面排列，静脉，网上有一个非常整齐的文章，谁能命名更大的数字？刷在图灵机和阿克曼function。

已经有很多好的答案了，但是我还没有看到任何人提出这样一个事实：在理论和实践的有机融合中，停止问题是真正可以解决的。

所以首先，停机问题的基本任务是编写一个任意的第二个程序，并确定第二个程序是否停止任意input。所以你说“是的，这个程序会停止这个input”或者“不会的”。事实上，在一般的情况下（在其他人似乎已经提供了这方面的证据）在图灵机上是无法解决的。真正的问题是你可以通过运行来发现是否会停下来（只是等到它停止），但是你不能真正发现是否有东西不会因为运行而停止（你会只是永远等待）。

这是图灵机上的一个问题，根据定义，图灵机具有无限的内存量，因此具有无限多的状态。但是，我们的电脑只有有限的内存。计算机上只有很多位。所以，如果你能以某种方式跟踪你在运行程序时看到的所有以前的状态（比特configuration），你可以保证你的检查器永远不会进入无限循环。如果辅助程序最终停止，你说“是的，这个程序将暂停在这个input”。如果在停止前两次看到相同的位configuration，则知道“不会”。可能不是很重要的技术，但是很高兴知道我们面临的真正“硬”问题在理论上比实践中要困难得多。

这是一个停止狗的问题的变种，除了程序，而不是狗，停止而不是吠叫。

你列举了一些简单的例子。

现在，想想所有其他案例。

有无数的可能scenrios，你将不得不列出所有。

除非你可以概括它。

这就是停止问题的来源。你如何概括它？

我build议阅读： http ： //en.wikipedia.org/wiki/Halting_problem ，尤其是http://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof ，以了解为什么这个问题不能解决algorithm的方式。

你的程序如何解决Collatz猜想？

从编程珍珠，通过Jon Bentley

4.6问题

5.certificate这个程序在其inputx是一个正整数时终止。

 while x != 1 do if even(x) x = x/2 else x = 3*x +1

假设你写一个algorithm可以检查任意一段代码，并判断它是否停止。

现在给你的algorithm本身检查。

问题的确切定义是，您需要编写一个程序来执行以下操作： – 执行一个任意程序 – 确定在程序中是否有任何有限的input

但是，这是一个非常高的酒吧。停止问题有许多部分的解决scheme，但没有一个通用的解决scheme。更糟的是，即使find部分解决暂停问题的scheme也是困难的：

英国广播公司h2g2文章停止问题

如果你真的解决了暂停问题，那么你可以在像rentacoder.com这样的网站上工作。几个月前，一位名叫ATuring的用户在他们中间发表了一篇文章，他提出了解决停机问题的合同。 🙂

你可能会发现，考虑那些不修剪自己的草坪的人的草坪的故事，并问自己是否割草。

还有一个例子。我最近碰到了一个叫hailstone号码的东西。这些数字与这些规则形成一个序列

 f(n) is odd - f(n+1) = 3*f(n)+1 f(n) is even - f(n+1) = f(n)/2

目前假定所有的起点最终都会达到1，然后重复4,2,1,4,2,1,4,2,1...但是没有证据可以certificate这一点。所以现在唯一的方法就是确定一个数字是否在被送入冰雹序列时终止，直到你到达1为止。

这是我如何理解暂停问题的关键。我的理解是，你不能确定知道一个程序将不会停止，除非你真的运行该程序 。所以你写的任何程序都可以给你一个肯定的停止问题的答案，但实际上却要运行程序。

遏制问题的重要性不在于问题本身的重要性; 相反，自动化testing在软件工程中几乎没有实际的用处（certificate程序暂停并不能certificate它是正确的 ，并且在任何情况下，假设的algorithm只能为给定的有限input提供certificate，而现实生活软件开发人员会对所有可能的有限inputtesting更感兴趣）。

相反，暂停问题是首先被certificate是不可判定的问题之一，这意味着在一般情况下不存在可用的algorithm。换句话说，在70多年前，图灵certificate了计算机无法解决的一些问题 – 不仅仅是因为没有find正确的algorithm，而是因为这样的algorithm在逻辑上是不存在的。