P-NP问题解决了吗?FindBugs解决了停止问题

Question

有一个名为FindBugs的工具，它可以检测给定程序/代码库中的无限个永不结束的循环。

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

给定任意计算机程序的描述，决定是否程序结束运行或继续永远运行

那么，这是否意味着停顿问题已经解决，或者停顿问题的一个子集已经解决？

Answer 1

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

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

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

它确实受到误报的影响：在许多情况下，findbug无法检测到非终结程序。

Answer 2

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

假设存在一个unieversal机器HALT(CODE, INPUT)，它暂停iffCODE在INPUT上。现在考虑一下：

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

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

假设CODE在CODE上停止，则程序将永远循环。。意思是。。。它不会停止
现在假设CODE没有在CODE上停止，您将得到。。。。它确实停止了。。

Answer 3

如果你要制作一个程序来分析同一平台上的程序，其限制与分析程序相同，那么这样的分析器是不可能存在的。这就是所谓的停顿问题。

也就是说，对于内存消耗和代码长度比分析程序少得多的程序来说，停止问题是可以解决的。我能停下来吗？所有2字节BrainFail程序的过程如下：

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