Towards a Theory of Bugs: The Ruliology of the Unexpected
I explore whether a scientific theory of software bugs exists, using ruliology and computational irreducibility. Even simple programs can behave unpredictably, creating bugs we cannot foresee without running them. This reveals fundamental tradeoffs between computational effectiveness and the difficulty of testing, verification, and security, including for AI-generated code.
When there's computational irreducibility nothing short of explicitly running a computation will determine what will happen.
- gjm11
Most of Wolfram's discussion of "bugs" is not about the following situation:
You want a program that does X. So you think about what a program that does X should look like, and write a program that does what you think should produce result X, but maybe you made some mistakes.
but about the following, to my mind completely different, situation:
You want a program that does X. So you write a bunch of random short programs and after a while you find one that looks on small examples as if it's doing X. You use that one, but maybe actually it doesn't always work.
The key difference here is that in the first case you try to make there not be bugs by understanding what the program is doing and in the second you try to make there not be bugs by looking at the program's output.
(Perhaps some super-extreme practitioners of test-driven development might argue for something like the latter. Perhaps some AI-driven programming is uncomfortably close to it. But it's not, generally, how people have produced and debugged software.)
Wolfram kinda tries to justify this perspective by saying:
"Fundamentally the only way to make sure a program will always do what you want is to understand everything it can do. But there’s a kind of paradox implicit in that: if you can really understand everything your program can do that basically means the program is doing something computationally reducible, and you probably in the end didn’t actually need to run the program with all its steps to get the result […]
- seanhunter
One of the frustrating things with the way Stephen Wolfram works is because he never actually defines anything it’s very hard to pin down what is actually interesting empirical science and what is data visualisation buggering around.
Here, before he starts, how do we know that the bugs in the Turing machine implementation of f(n)=n+1 are in any way representative of bugs in a normal computation? He seems to be generating random state machines and then evaluating them and picking ones which are nearly but not quite correct implementations of f(n)=n+1. Is that like a normal “honest” software bug? Is it like a deliberate software sabotage like you might look for when evaluating a software supply chain risk? Is it like the sort of vulnerability you might see when fuzzing? As far as I can see, there’s no reason to think it’s like any of these.
More broadly, since the “Principle of Computational Equivalence” and “computational irreducibility” are referred to as touchstones but are never actually defined or properly established how are we supposed to treat them? Interesting conjectures? Actual axioms? Something in between?