Software Programs, Debugging Software Programs???

[Stephen3141]

AI models still struggle to debug software, Microsoft study shows | TechCrunch

Even some of the best AI models today still struggle to debug software, a Microsoft study shows.

techcrunch.com

WOW! APPARENTLY MICROSOFT IS BEGINNING TO DISCOVER THE BASIC
THEOREMS OF COMPUTER SCIENCE!!!

What sort of ignorant managers, does Microsoft have, if they have not grasped
the basic limits of software algorithms!?

Specifically, Computer Science has demonstrated that there is NO algorithm that
can PREDICT whether or not another software algorithm will ever "halt". By "halt",
Computer Science means "achieve its goals," or quit before it reaches its goals.
THIS IS THE BASIC HALTING PROBLEM, IN COMPUTER SCIENCE.

Any competent software programmer, should know this.
---------- ------------

IT FOLLOWS, that it is impossible to write a (fixed) algorithm that can "debug"
any other software algorithm.

This is very basic Computer Science knowledge.
---------- ----------

THERE ARE HUGE PROBLEMS THAT FOLLOW, IN THE CURRENT AI ALGORITHM
DESIGNS!!!!

For example...

1 (Unless a human expert defines the data that an AI tool will train on) an AI tool
will not be able to determine WHEN it has incorporated enough data, to reliably
solve a problem. (When does the incorporation of data HALT?)

2 An AI algorithm will NOT be able to determine the RELEVANCY of the data that
it has incorporated. This is a basic part of a worldview. (When does the search
for relevant data, HALT?)

3 The AI algorithm will NOT be able to determine a hierarchy of AUTHORITIES
that DO define what data is relevant, to solve a certain problem. (When does
the search for authoritaties, HALT?)

4 The AI algorithm will NOT be able to determine the BOUNDARIES of the
competency of one of these "machine learning" algorithms to make decisions.
(Beyond these boundaries, the algorithm will be HALLUCINATING, and could be
an active danger to anyone who believes its answers, or a dangerous driver
for "agents".)
---------- ----------

Philosophers ask these questions, and can address them.
Intelligent and educated Computer Science grads can ask these questions,
and can lay out a human plan to answer them.
Managers of AI tools and agents, IT SEEMS, often don't even know that these
questions exist, or how to go about making a plan to discover the answers.
Readers without the self-discipline to even read this comment (that is, their
attention span already does not allow them to read and think about a comment
this long, will NEVER be able to contemplate the basics of Computer Science.

Maybe the big AI software companies should start to hire managers, who at
least grasp the basic theorems and postulates AND PROBLEMS of Computer Science.

AND THAT INCLUDES, the problems that Computer Science has demonstrated
to be UNDECIDABLE, or COMPUTATIONALLY INTRACTIBLE.

SHAME ON YOU! BIG SOFTWARE COMPANIES!!!
Go and learn some basic Computer Science principles.

 

[Stephen3141]

For those who want a quick overview of the Halting Problem...

Wikipedia has this to say on the Halting Problem...

"In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs. The problem comes up often in discussions of computability since it demonstrates that some functions are mathematically definable but not computable.

A key part of the formal statement of the problem is a mathematical definition of a computer and program, usually via a Turing machine. The proof then shows, for any program f that might determine whether programs halt, that a "pathological" program g exists for which f makes an incorrect determination. Specifically, g is the program that, when called with some input, passes its own source and its input to f and does the opposite of what f predicts g will do. The behavior of f on g shows undecidability as it means no program f will solve the halting problem in every possible case.

Background​

[edit]
The halting problem is a decision problem about properties of computer programs on a fixed Turing-complete model of computation, i.e., all programs that can be written in some given programming language that is general enough to be equivalent to a Turing machine. The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input. In this abstract framework, there are no resource limitations on the amount of memory or time required for the program's execution; it can take arbitrarily long and use an arbitrary amount of storage space before halting. The question is simply whether the given program will ever halt on a particular input.

For example, in pseudocode, the program

while (true) continue
does not halt; rather, it goes on forever in an infinite loop. On the other hand, the program

print "Hello, world!"
does halt.

While deciding whether these programs halt is simple, more complex programs prove problematic. One approach to the problem might be to run the program for some number of steps and check if it halts. However, as long as the program is running, it is unknown whether it will eventually halt or run forever. Turing proved no algorithm exists that always correctly decides whether, for a given arbitrary program and input, the program halts when run with that input. The essence of Turing's proof is that any such algorithm can be made to produce contradictory output and therefore cannot be correct.

Programming consequences​

[edit]
Some infinite loops can be quite useful. For instance, event loops are typically coded as infinite loops.[1] However, most subroutines are intended to finish.[2] In particular, in hard real-time computing, programmers attempt to write subroutines that are not only guaranteed to finish, but are also guaranteed to finish before a given deadline.[3]

Sometimes these programmers use some general-purpose (Turing-complete) programming language, but attempt to write in a restricted style—such as MISRA C or SPARK—that makes it easy to prove that the resulting subroutines finish before the given deadline.[citation needed]

Other times these programmers apply the rule of least power—they deliberately use a computer language that is not quite fully Turing-complete. Frequently, these are languages that guarantee all subroutines finish, such as Rocq.[citation needed]

Common pitfalls​

[edit]
The difficulty in the halting problem lies in the requirement that the decision procedure must work for all programs and inputs. A particular program either halts on a given input or does not halt. Consider one algorithm that always answers "halts" and another that always answers "does not halt". For any specific program and input, one of these two algorithms answers correctly, even though nobody may know which one. Yet neither algorithm solves the halting problem generally.

There are programs (interpreters) that simulate the execution of whatever source code they are given. Such programs can demonstrate that a program does halt if this is the case: the interpreter itself will eventually halt its simulation, which shows that the original program halted. However, an interpreter will not halt if its input program does not halt, so this approach cannot solve the halting problem as stated; it does not successfully answer "does not halt" for programs that do not halt." "

 

[The Liturgist]

Specifically, Computer Science has demonstrated that there is NO algorithm that
can PREDICT whether or not another software algorithm will ever "halt". By "halt",
Computer Science means "achieve its goals," or quit before it reaches its goals.
THIS IS THE BASIC HALTING PROBLEM, IN COMPUTER SCIENCE.

But you know we have debugging systems using neural networks that do detect errors; while it is true we cannot predict if a program will halt on input, we can nonetheless catch a large range of errors, for example, memory allocation errors, which are not related to the halting problem. Another area where AI can help is in evaluating multithreaded software for known mistakes involving resource contention, where for example a shared resource is not properly protected and race conditions to occur.

The halting problem is not the cause of most software bugs, but rather is a simple fact related to computability, just like how we cannot compute the Busy Beaver numbers past a certain point within the predicted lifespan of the universe since they grow so exponentially quickly. But these are first year curiosities that have very little real world application.

The most common bugs in C/C++ applications involve errors pertaining to manual memory management, for example, misuse of pointers, malloc() and free(). Also buffer overflows and other situations which can result in accessing memory you didn’t intend to, or undefined system behavior. An LLM AI can absolutely identify the more obvious errors of this sort, although for that matter I suppose one could also do it using pattern matching algorithms. But in a sense, LLMs are the ultimate Grep, since what they excel at is pattern matching according to their training data.

If Microsoft did think they could solve the halting problem with an AI, that would be very stupid, because humans can’t solve the halting problem (it was discovered by Turing simulating the behavior of a very simple sort of computer by hand with basic math).

 

[Stephen3141]

It is easy to detect SOME errors in computer code, such as syntax problems.

But it is impossible to predict if a program has encoded a wrong methodology
in the computer code, unless the program doing the checking is an expert in every
sort of discipline.

The Halting Problem remains.

 

[The Liturgist]

It is easy to detect SOME errors in computer code, such as syntax problems.

But it is impossible to predict if a program has encoded a wrong methodology
in the computer code, unless the program doing the checking is an expert in every
sort of discipline.

A wrong methodology could mean anything including poor architectural choices. I would say every software program written in BASIC or Pascal or COBOL has fundamental methodological errors but at the same time such programs work, indeed there remains some important legacy COBOL code out there doing mission critical tasks (I greatly respect Admiral Grace Hopper; the only one of the first three high level languages which hasn’t become dated and lacking compared to newer languages is LISP, but only some dialects of, and ironically it was, when first introduced, the slowest and least usable of the three, and furthermore the original design for the language was never completely implemented, since S-expressions were sufficiently powerful and elegant by themselves).

One can use software however to check for errors. Indeed compilers do this automatically for a large number of errors, since its better for a program to not build than for it to build with a subtle bug that can corrupt data.

The Halting Problem remains.

I’m not denying that, but how many times have you had a broken build or error condition in your code due to the halting problem as opposed to improper API calls, memory leaks, buffer overflows and underruns, dividing by zero, race conditions between multiple threads and problems with third party libtaries or dependencies?

In the wild, the halting problem just doesn’t show up that much. One is much more likely to make a mistake with pointers, concurrency, pattern-matching, and for that matter with system architecture than write a program that halts or does not halt unexpectedly.

 

[The Liturgist]

I should add that although rare, certain bugs can reflect halting-related issues:

• Infinite loops (e.g., bad while condition).
• Unbounded recursion causing stack overflows.
• Deadlocks where progress is impossible.
• Non-terminating state machines due to bad logic or forgotten base cases.

But even these tend to be fixable through code inspection, testing, or dynamic analysis — and they occur due to poor implementation, not undecidability in the formal Turing sense.

By the way debugging and code analysis software is a big business. Coverity etc specialize in it. And like I said, every compiler or interpreter is designed to catch as many bugs at possible during compilation or at runtime respectively.