3

有一个工具叫做FindBugs它可以检测给定程序/代码库中的无限循环。

这意味着FindBugs可以通过分析代码来检测程序是否会结束。停止问题是定义以下问题的问题：

给定任意计算机程序的描述，决定程序是完成运行还是永远继续运行

那么这是否意味着停止问题已解决或停止问题的子集已解决？

4

3 回答 3

6

不，它没有解决。Findbugs 只发现一些无限循环的情况，比如这个：

public void myMethod() {
    int a = 0;
    while (true) {
        a++;
    }
}

IIRC，它遭受的唯一误报myMethod是，如果从未调用过上述方法，在这种情况下，您仍然希望将其删除，因为它是死代码。

它确实存在误报：很多情况下 findbugs 无法检测到无休止的程序。

于 2013-11-19T08:57:26.033 回答
1

想象一下，您有一个始终检测无限循环的工具。

假设存在一个停止当且仅当停止的通用机器 。现在考虑一下：HALT(CODE, INPUT) CODEINPUT

  1. if HALT(CODE, CODE), 永远循环
  2. else halt

如果CODE停止CODE，你会得到一个矛盾，如果它没有。为什么？

假设CODE在 停止CODE，那么程序将永远循环......这意味着......它不会停止..
现在假设CODE 不会停止CODE，你会明白......它确实停止了......

于 2013-11-19T09:00:23.437 回答
0

如果您要编写一个程序来分析与分析程序具有相同限制的同一平台的程序，那么这种分析器是不可能存在的。这被称为停机问题。

话虽如此，对于内存消耗和代码长度比分析程序少得多的程序，停止问题是可以解决的。例如。我可以停下来吗？所有 2 字节BrainFuck程序的程序如下：

;; takes a valid 2 byte BF-program
;; and returns if it will halt
(define (halt? x)
  (cond ((equal? x "[]") #f)
        (else #t)))

一个更大的例子是通过制作解释器和散列内存状态和 pc 位置。如果找到先前的状态，则它是一个无限循环。即使有一个非常好的数据模型，解释器使用的内存也必须比它解释的内存大得多。

我正在考虑不断折叠程序，并且停止问题成为一个问题。我的想法是拥有一个数据结构，该结构具有已看到 AST 中特定分支的次数，并且具有非常大的截止限制。因此，如果解释器在一个分支上多于截止，它将最终出现在编译程序中，而不是计算中。它占用的内存要少得多，并且会确定程序的某些或所有部分肯定会返回（停止）。

想象一下这段代码：

(define (make-list n f)
   (if (zero? n)
       '()
       (cons (f) (make-list (- n 1) f))))

(define (a)
  (b))

(define (b)
  (c))

(define (c)
  (b))

(display (make-list 4 read))
(display (make-list 4 a))

这实际上是非常糟糕的代码，因为您不知道输入可能会得到哪个顺序。编译器可以选择最好的，它可能会变成：

(display-const "(")
(display (read))
(display-const " ")
(display (read))
(display-const " ")
(display (read))
(display-const " ")
(display (read))
(display-const ")")
(display (cons (b) (cons (b) (cons (b) (cons (b) '())))) ; gave up on (b)
于 2013-11-19T11:40:35.367 回答