Towards a Theory of Bugs: The Ruliology of the Unexpected—Stephen Wolfram Writings

Recent |

Categories

Artificial Intelligence<br>Big Picture<br>Biology<br>Companies & Business<br>Computational Science<br>Computational Thinking<br>Data Science<br>Education<br>Future Perspectives<br>Historical Perspectives<br>Language & Communication<br>Life & Times<br>Life Science<br>Mathematica<br>Mathematics<br>Multicomputation<br>New Kind of Science<br>New Technology<br>Personal Analytics<br>Philosophy<br>Physics<br>Ruliology<br>Software Design<br>Wolfram|Alpha<br>Wolfram Language<br>Other

&times;

Contents

Top

“My Program Did the Wrong Thing!”

Bugs in Turing Machines

What Counts as a Bug?

A Cellular Automaton Example

Can One Tell If There’s Going to Be a Bug?

But What about Formal Proofs?

Computational Irreducibility and Bugs

Did I Test Enough Cases? The Failure of Ruliological Induction

Some Typical Ruliological Surprises

Mathematical “Bugs”

Bugs in Practice

Thanks

Towards a Theory of Bugs: The Ruliology of the Unexpected

Towards a Theory of Bugs: The Ruliology of the Unexpected

July 21, 2026

“My Program Did the Wrong Thing!”

Bugs are a ubiquitous phenomenon in the software world. And—essentially by definition—each one of them is somehow unique and unexpected. But—particularly given their ubiquity—one might wonder whether there could perhaps be some kind of general “scientific” theory that could be developed about them. My goal here is to explore that question. And what we’ll find is that there are indeed foundational ways to think about bugs (and “correct programs”)—using concepts like computational irreducibility (and computational reducibility).

The things we’ll discuss will give us a sense of the fundamental tradeoffs between computational effectiveness and the propensity for bugs—as well as of strategies for the detection of bugs, and expectations about the difficulty of testing. Along the way, we’ll be able to illuminate some underlying issues associated both with software verification and with computer security—as well as about code generated by AI systems.

In a sense, the key to what we’ll do is to realize that the fundamental phenomenon of bugs already occurs even in very simple programs. And that means that we can use the methods and intuition of ruliology to study foundational questions about bugs.

When we write a program we normally know what we want the program to do. And if in some case it unexpectedly doesn’t do it, we consider that a bug. In more abstract terms, we normally have in our minds a representation for what the program should do. And for it to fit in our minds this has to be computationally quite simple. But then the question is whether the computational process associated with actually running the program is somehow correspondingly simple. If it is, then it’s possible for it to narrowly follow the representation we have.

But a big surprise—captured by my Principle of Computational Equivalence—is that even programs (or fragments of them) that are very simple in their structure can end up doing computation that is in a sense as sophisticated as anything. And the result is that such programs can exhibit computational irreducibility—which means that they will inevitably be able to do things we can’t foresee and don’t expect, and that we will consider to be bugs.

But even if we humans can’t do it unaided, can we expect to build automated systems—with AI or otherwise—that can root out such bugs? There are—as we’ll discuss—necessarily “pockets of computational reducibility” in which we can expect to make progress. But the key point is that “lurking at the edges” is computational irreducibility. And when there’s computational irreducibility nothing short of explicitly running a computation will determine what will happen. And that means that unless we’ve already run our program in a particular case, we won’t be able to know for sure what it will do. And when it does things we don’t want, we’ll call those things “bugs”.

Bugs in Turing Machines

To begin our explorations, we’re going to look at a very simple and longstanding model of computation: Turing machines. Consider the (3-state, 2-color) Turing machine with rule:

Imagine we put the binary digits of an integer n initially on the tape of the Turing machine, then run the machine and see what number is on its tape when its head goes further to the right than it started:

Looking at these examples, we’d probably conclude that the Turing machine is computing the function n n + 1. But let’s see what happens if we try larger inputs:

And yes, for input 7, there’s a bug! Instead of outputting 7 + 1 = 8, the Turing machine outputs 9.

Plotting the values the Turing machine computes, we see a succession of little glitches:

The glitches turn out to appear at values of n of the form 8k – 1 (and their magnitude ends up being Floor[2^(IntegerExponent[k + 1, 2] + 3)/7]). If we look at the actual, detailed operation of the Turing machine we see what “causes a bug” in these cases. For values of n where...