标签: halting-problem

while在Java中查看以下无限循环.它会导致它下面的语句出现编译时错误.

while(true) {
    System.out.println("inside while");
}

System.out.println("while terminated"); //Unreachable statement - compiler-error.

以下相同的无限while循环,但工作正常,并不会发出任何错误,我只是用布尔变量替换条件.

boolean b=true;

while(b) {
    System.out.println("inside while");
}

System.out.println("while terminated"); //No error here.

在第二种情况下,循环后的语句显然无法访问,因为布尔变量b为true,编译器根本不会抱怨.为什么？

编辑:下面的版本while陷入了无限循环,但是对于它下面的语句没有发出编译器错误,即使if循环中的条件总是false因此,循环也永远不会返回并且可以由编译器在编译时本身.

while(true) {

    if(false) {
        break;
    }

    System.out.println("inside while");
}

System.out.println("while terminated"); //No error here.

while(true) {

    if(false)  { //if true then also
        return;  //Replacing return with break fixes the following error.
    }

    System.out.println("inside while");
}

System.out.println("while terminated"); //Compiler-error - unreachable statement. …

When have you ever personally come upon the halting problem in the field? This can be when a co-worker/boss suggested a solution which would violate the fundamental limits of computation, or when you realized yourself that a problem you were trying to solve was, in fact, impossible to solve.

我最近想出来的时候是研究类型检查器.我们班级意识到编写一个完美的类型检查器是不可能的(一个可以接受所有运行没有类型错误的程序,并拒绝所有运行类型错误的程序),因为这实际上可以解决暂停问题.另一个是当我们在同一个类中意识到在类型检查阶段不可能确定除法是否会出现零,因为检查一个数字在运行时是否为零,也是暂停问题的一个版本.

每当人们询问与编程有关的暂停问题时,人们会回答:"如果你只是添加一个循环,那么你就有了停止程序,因此无法自动完成任务 "

说得通.如果你的程序有一个无限循环,那么当你的程序运行时,你无法知道程序是否仍在处理输入,或者它是否只是无限循环.

但其中一些似乎反直觉.如果我正在编写一个暂停问题求解器,它将源代码作为输入,那该怎么办？rascher@localhost$ ./haltingSolver source.c

如果我的代码(source.c)看起来像这样:

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

看起来我的程序看起来很容易."查看循环,看看条件.如果条件只是基于文字而没有变量,那么你总是知道循环的结果.如果有变量(例如while(x <10)),看看是否这些变量是永远修改的.如果没有,那么你总是知道循环的结果."

当然,这些检查不会是微不足道的(计算指针算术等),但这似乎不可能.例如:

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

可以检测到.以及 - 尽管不是轻微的:

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

那么用户输入呢？这就是踢球者,这就是让程序无法预测的原因.

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

现在我的程序可以说:"如果用户输入10或更高,程序将停止.在所有其他输入,它将再次循环."

这意味着,即使有数百个输入,也应该能够列出程序停止的条件.实际上,当我编写程序时,我总是确保有人能够终止它!我并不是说由此产生的条件清单是微不足道的,但对我来说似乎并不可能.您可以从用户那里获取输入,使用它们来计算指针索引等等 - 但这只会增加条件的数量以确保程序终止,不会使它们无法枚举. …

几乎所有使用的编程语言都是图灵完备,虽然这提供了语言来表示任何可计算的算法,但它也有自己的一组问题.看到我写的所有算法都打算停止,我希望能够用一种语言来代表它们,以保证它们会停止.

正则表达式用于匹配字符串和有限状态机在使用时词法,但我不知道是否有这不是图灵完整更普遍的,广泛的语言吗？

编辑:我应该澄清,通过'通用'我不一定希望能够在语言中编写所有停止算法(我不认为这样的语言会存在)但我怀疑有共同的线程停止可以推广的证明,以产生一种语言,保证所有算法都停止.

还有另一种解决这个问题的方法 - 消除理论上无限记忆的需要.一旦限制了机器允许的内存量,机器所处的状态数是有限且可数的,因此您可以确定算法是否会停止(通过不允许机器进入之前的状态) ).

我有一个庞大的正则表达式集合,当匹配时调用一个特定的http处理程序.一些较旧的正则表达式是无法访问的(例如a.c* ? abc*),我想修剪它们.

是否有一个库给出两个正则表达式会告诉我第二个是否是第一个的子集？

我一开始并不确定这是否具有可判定性(它的气味就像一个不同名称的停止问题).但事实证明它是可判定的.

在课堂上,我们了解了暂停问题,图灵机器,减少等等.许多同学都说这些都是抽象和无用的概念,而且知道它们并没有真正的意义(即,一旦课程结束,你就会忘记它们结束而不是失去任何东西).

为什么理论有用？你有没有在日常编码中使用它？

我用MATLAB脚本语言编写了一个简单的brainfuck解释器.它被随机的bf程序执行(作为遗传算法项目的一部分).我面临的问题是,程序在相当多的情况下都会出现无限循环,因此GA会陷入困境.
所以,我需要一种机制来检测无限循环并避免在bf中执行该代码.
一个明显的(微不足道的)案例是我有的时候

[]

我可以检测到这一点并拒绝运行该程序.
对于非平凡的情况,我发现基本思想是:确定循环的一次迭代如何改变当前单元格.如果变化为负,我们最终将达到0,所以这是一个有限的循环.否则,如果更改是非负的,则它是无限循环.
对于单个循环来说,实现这一点很容易,但是使用嵌套循环会变得非常复杂.例如,(在下面的(1)中指的是单元格1的内容等)

++++ Put 4 in 1st cell (1)
>+++ Put 3 in (2)
<[   While( (1) is non zero)
    --   Decrease (1) by 2
    >[   While( (2) is non zero)
        -    Decrement (2)
        <+   Increment (1) 
    >]   
    (2) would be 0 at this point
    +++  Increase (2) by 3 making (2) = 3
<]   (1) was decreased by 2 and then increased by 3, so net effect is increment

因此代码会一直运行.然而,对单元格1上的+和 - 的完成次数的天真检查会说-s的数量更多,因此不会检测到无限循环. …

在这个关于NP,NP-hard和NP-complete定义的问题的答案中,Jason提出了这样的主张

停止问题是经典的NP难问题.这是给出程序P和输入I的问题,它会停止吗？这是一个决策问题,但它不在NP中.很明显,任何NP完全问题都可以简化为这个问题.

虽然我同意停止问题在直觉上比NP中的任何问题都要困难得多,但老实说,我无法提出一个正式的数学证明,即停止问题是NP难的.特别是,我似乎无法找到从NP(或至少任何已知的NP完全问题)中的每个问题的实例到停止问题的多项式时间多对一映射.

是否有一个直截了当的证据表明停止问题是NP难的？

我正在通过Sipser 对计算理论介绍中的停止问题进行证明,我主要关注的是下面的证据:

如果TM M不知道它何时循环(它不能接受或拒绝这就是为什么TM对所有字符串都是图灵可识别的),那么决策者H怎么能决定M是否可能在循环中？当TM D进行处理时,同样的问题将继续存在.

暂停问题对于图灵完整语言是无法解决的,并且对于一些非TC语言(例如它总是停止的正则表达式),它可以简单地解决.

我想知道是否有任何语言都具有停止和不停止的能力,但允许一种算法可以确定它是否停止.