Search code examples
algorithmfindbugshalting-problemp-np

P-NP problems solved? FindBugs solves the halting prob?


There is a tool called FindBugs it can detect infinite never ending loops in a given program/ code base.

This implies FindBugs can detect if a program will end or not by analyzing the code. Halting problem is the problem defining that:

Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever

So does this imply that the halting problem is solved or a subset of the halting problem is solved?


Solution

  • No, it's not solved. Findbugs only finds some of the cases of infinite never ending loops, such as this one:

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

    IIRC, the only false negative it suffers from is, if the above method myMethod is never called, in which case you 'll still want to delete it as it's dead code.

    It does suffers from false positives: there are many cases of non-ending programs that findbugs will not detect.