到底是什么问题?

编辑(比原始答案晚很多):markcc of Good Math, Bad Math 最近写了一篇 excellent discussion 用具体的例子来说明中止问题。

停顿问题基本上是 正式的询问方式 是否任意程序 最终会停止。

换句话说,你能写一个 一个叫做停止预言的程序, 停止Oracle(程序,输入),其中 如果程序(输入)将 最后停下来 如果不会的话是假的?

答案是:不,你可以。

关于停止问题的输入是相关的还是有害的:是的,输入是重要的。另外,我看到“无限”被用在“任意”更正确的地方,这似乎有些混乱。

实例 :假设您在一个qa岗位上工作,并且您要编写一个停止检查程序(也称为oracle),该程序将确认 任意的 由开发团队(D)和任何 任意的 由最终用户(i)提供的输入,当给定输入i时,程序d最终将停止。

提示管理器声音 :“呵呵,那些愚蠢的用户,让我们确保无论他们输入什么垃圾,我们的服务器任务永远不会以无休止的循环结束。就这样吧,代码猴!”

这看起来是个好主意,对吧?你不想让你的服务器挂断,对吧?

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

Mark使用代码而不是输入来说明问题:

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

在我在评论中的讨论中,我采用了恶意输入操作的方式来强制解决一个无法解决的问题。马克的例子要优雅得多,他用停滞不前的神谕来战胜自己:

所以,欺骗者的输入实际上是 两个元素的列表:第一个 是一个被提议停职的先知。这个 其次是另一个输入。什么 停止杀人是问神谕: 你认为我会停止输入吗?–157;。 如果神谕说,是的,你会 暂停,然后程序进入 无限循环。如果神谕说不, 你不停,它就停。所以没有 不管甲骨文怎么说, 错了。

换句话说,在没有欺骗、重新格式化输入、可数/不可数无穷大或任何其他干扰的情况下,mark已经编写了一段可以击败 任何 停止Oracle程序。你不能写 oracle 这回答了是否 Deceiver 永不停歇。

原始答案:

从伟大的 Wikipedia 以下内容:

在可计算性理论中,停止 问题是一个决策问题 可以这样说:给定 程序和有限元的描述 输入,决定程序是否 完成跑步或将永远跑步, 考虑到这个因素。

阿兰图灵在1936年证明 解停顿的一般算法 所有可能的程序输入问题 对不能存在。我们说 停止问题是不可判定的结束 图灵机器。科普兰(2004) 将实际术语定义为停止 马丁·戴维斯有问题。

关键的一点是你不能控制程序或输入。你拿到了这些,由你来回答这个问题。

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

为了解决停顿问题,你必须开发一个算法来确定 任何武断的 程序停止 对于任意输入 ,而不仅仅是示例中相对简单的情况。

这里有一个简单的解释,证明停止问题是不可判定的。

假设您有一个程序h,它计算程序是否停止。h有两个参数,第一个是对程序p的描述,第二个是输入,如果p停止输入i,i.h返回true,否则返回false。

现在编写一个程序,p2,它将另一个程序p3的描述作为输入。p2调用h(p3,p3),如果h返回true则循环,否则停止。

当我们运行p2(p2)时会发生什么?

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

它被打得死去活来 poetic proof ,以 刘易斯卡罗尔 苏斯博士杰弗里·普勒姆 Language Log 名声)。

有趣的事。这里有一个味道:

这是不好用的伎俩,而且很简单。
我将定义一个过程,称为q,
这将使用PS预测停止成功
挑起一场可怕的逻辑混乱。

…

无论P的表现如何,Q都会抓住它:
q使用ps输出使p看起来很愚蠢。
不管P说什么,它都不能预测Q:
p错时是对的,真时是错的!

有一个很好的证据 Halting Problem 在维基百科上。

要确切地说明为什么仅仅对循环应用某些技术是不够的,请考虑以下程序(伪代码):

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吗?

Think Carefully 是的。

如果碰巧你在争夺菲尔兹勋章,想象一下 these problems 代替上面的。

如果只添加一个循环,则程序将停止,因此无法自动执行任务

听起来像是有人过度概括了停止问题的应用。有很多特殊的循环可以证明是终止的。有研究可以执行广泛的类程序的终止检查。例如,在coq中,您仅限于可以证明终止的程序。微软有一个名为终结者的研究项目,它使用各种近似来证明程序将终止。

但是,记住,停止的问题不仅仅是玩具的例子。这两种方法都不能解决一般的“停止问题”,因为它们并不适用于所有程序。

问题在于停机问题表明,存在程序,你无法知道它们是否会在不运行它们的情况下终止,这意味着你可能永远无法决定是否停止。

可以或不可以停止的程序示例(在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年,但没有证据。

图灵的一个很好的例子是自引用的——假设有一个程序可以检查另一个程序并确定它是否会停止。将停止的程序检查器本身放入停止的程序检查器-它应该做什么?

关于子点“people respond with”,如果您只添加一个循环,您就得到了停止程序,因此您无法自动执行任务“,我将添加以下详细信息:

那些说你不能用算法计算任意程序是否会停止的帖子对于图灵机器来说是绝对正确的。

问题是,并非所有程序都需要图灵机。这些程序可以用概念上“较弱”的机器来计算——例如,正则表达式可以完全由一个有限状态机来实现,它 总是 停止输入。这不是很好吗?

我敢打赌,当人们说“添加一个循环”时,他们试图表达这样的想法:当一个程序足够复杂时,它需要一个图灵机,因此停止问题(作为一个想法)就适用了。

这可能与问题有点相悖,但我相信,考虑到问题的细节,这一点值得指出。:)

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

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

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;
}

所以在这个例子中,我们可以编写一个程序来完成与我们神奇的停止方法完全相反的任务。如果我们以某种方式确定一个给定的程序将停止,我们就跳到一个无限循环中;否则,如果我们确定该程序处于一个无限循环中,我们就结束该程序。

无论您执行多少输入检查,都没有可能的解决方案来确定每个编写的程序是否停止。

到目前为止有很多有趣的具体例子/类比。如果你想更深入地了解背景,有一本关于图灵原著的好书, The Annotated Turing 查尔斯·佩佐尔德。

在一个相关的,横向排序,静脉,网上有一篇非常整洁的文章, Who Can Name the Bigger Number? 在图灵机器和阿克曼函数上的刷子。

已经有很多好的答案了,但是我还没有看到有人提到这样一个事实:在理论和实践的选择性融合中,停顿问题确实是可以解决的。

因此,首先,停止问题基本上是编写一个程序的任务,它接受任意的第二个程序,并确定第二个程序是否会在任意输入时停止。所以你说“是的,这个程序会在这个输入上停止”或者“不,它不会”。事实上,在图灵机器上一般情况下(其他人似乎已经提供了这方面的证据)是无法解决的。真正的问题是,你可以通过运行它来确定某个东西是否会停止(只是等到它停止),但是你不能通过运行它来确定某个东西是否不会停止(你只需要一直等待)。

这是图灵机器上的一个问题,根据定义,图灵机器有无限多的内存,因此有无限多的状态。然而,我们的计算机只有有限的内存。计算机上只有这么多位。因此,如果您可以在运行程序时以某种方式跟踪以前看到的所有状态(位配置),那么您可以保证您的检查器永远不会进入无限循环。如果第二个程序最终停止,您会说“是,此程序将在此输入上停止”。如果在同一位配置停止前看到两次,就知道“不会”。可能技术上并不重要,但很高兴知道,很多时候,我们面临的真正“困难”的问题在理论上比在实践上更困难。

它是 halting dog problem ,除了用程序代替狗和停止而不是吠叫。

从另一个角度证明

假设我们有一个cpu,它有mov、add、jmp等指令,但没有输入或输出。我们有记忆。不像其他CPU,这个CPU有另一个寄存器,叫做 帕拉雷格 .这个寄存器就像一个文件,我们可以把无限的内容移动到它里面,得到它的大小,寻找到它的中间,从中删除一些内容,这些都是通过一些额外的指令来完成的。

在开始之前,让我们定义一些单词。一个 程序 是一堆指令,这是一个字符串。在我们运行一个程序之前,我们清除所有的寄存器和内存为零,除了parareg,它保存参数(字符串),然后将程序放入内存位置零,并将ip寄存器设置为零。一个 过程 当程序运行时。

现在,暂停问题可以这样表述:给定任何一个名为proobj的程序(如果它接受参数para0,我们在它的第一行添加一条指令:mov parareg,para0),是否有一个程序以proobj为参数,并可以决定当proobj开始在设置为零的parareg上运行时proobj是否会停止?

假设我们有这样一个程序,叫做p1。然后我们可以创建另一个程序,称为p2,它接受参数para0。通过p1,我们可以判断内容为para0、参数为para0的程序是否会停止(我们是这样做的)。构造一个程序,其第一行是[mov parareg,para0],其余的是para0。将此程序命名为pro0。然后我们将parareg设置为pro0并调用p1。)如果它会停止,我们让p2进入一个无限循环,否则我们让p2停止。

如果我们将p2放入parareg并运行p2,进程是否会停止?如果它停止,从p2的定义来看,我们知道当我们将p2放入parareg并运行p2时,它不应该停止;同样,如果它不停止,我们知道当将p2放入parareg并运行p2时,它应该停止。然后我们可以说没有p2,也没有p1。

你列举了几个简单的例子。

现在,想想其他的案子。

有无数可能的场景,你必须把它们都列出来。

当然除非你能概括它。

这就是停止问题的症结所在。你如何概括它?

你的程序如何解决 Collatz conjecture 是吗?

从 Programming Pearls ,作者Jon Bentley

4.6问题

5个。证明当程序的输入x为正整数时,程序终止。

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

我建议你读一下: http://en.wikipedia.org/wiki/Halting_problem ,尤其是 http://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof 为了理解为什么这个问题不能用算法的方法解决。

假设您编写了一个算法,可以检查任意一段代码并判断它是否停止。

现在让你的算法自己检查一下。

问题的确切定义是,您需要编写一个执行以下操作的程序: -接受任意程序 -确定程序在给定程序的任意有限输入时是否停止

然而,这是一个非常高的标准。中止问题有许多局部解,但没有一般解。更糟糕的是,即使找到部分解决停顿问题的程序也很困难:

BBC h2g2 article on the halting problem

如果你真的解决了停止问题,那么在rentacoder.com这样的网站上就可以为你工作。几个月前,有一个名叫aturing的用户发了一篇关于其中一个的帖子,他提供了一份解决停机问题的合同。:)

你可能会发现,想想那个给不自己修剪草坪的人修剪草坪的人的故事,问问自己是否自己修剪草坪,会有帮助。

又是一个例子。我最近碰到一个叫冰雹数字的东西。这些数字与这些规则形成一个序列

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... 但是没有证据证明这一点。所以现在唯一确定一个数字在进入冰雹序列时是否终止的方法是 实际计算它 直到你1点到达。

这是如何 我 了解停止问题。我怎么知道你不能 当然 知道一个程序不会停止,除非你 实际运行程序 .所以你写的任何能给你答案的程序 当然 对于停止问题,必须实际运行程序。

停止问题的重要性并不在于问题本身的重要性;相反,自动化测试在软件工程中几乎没有实际应用(证明一个程序停止并不能证明它是 对的 ,并且在任何情况下,假设算法只为给定的有限输入提供证据,而实际的软件开发人员更感兴趣的是 全部的 可能的有限输入)。

相反,停顿问题是最早被证明的问题之一。 不可判定的 这意味着在一般情况下没有算法存在。换句话说,图灵在70多年前就证明了计算机无法解决的一些问题——不仅仅是因为还没有找到正确的算法,而是因为这种算法不能逻辑上存在。