“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 the Turing machine “operates correctly” its head sweeps to the left, if necessary propagating a carry bit, then, when it sweeps to the right, it makes no further changes to the configuration on the tape. But if n is a number whose binary representation ends in 111 (i.e. it is a number of the form 8k – 1, equal to 7 modulo 8), then when the head sweeps to the right it does “little extra jigs” and “scribbles incorrect digits” onto the tape:

There are plenty of “correct” Turing machines that compute the function n + 1; indeed, with 3 states and 2 colors there are actually 8934 of them, most operating in fairly simple ways

but some operating in what at first seem like almost absurdly complex ways (though in the end—as the squashed renderings on the right show—they’re just nested):

But if a Turing machine like this is “going to have a bug”, how far does one have to go before it shows up? Here’s a plot of the number of 3-state, 2-color machines that “correctly compute” n + 1 up to a given value of n

and here’s a summary of where the “first bugs” occur:

The “most insidious” bugs do not occur until n = 15. An example of a machine with such a bug is:

The sequence of values in this case is:

And, yes, if one runs this machine for inputs from 0 to 14 everything works just fine—but suddenly at n = 15, instead of giving output 15 + 1 = 16, the machine gives 20! (The glitches continue at all inputs of the form 16k – 1, i.e. having 1111 at the end of their binary representations.)

What about for larger Turing machines? Of the 4 billion or so 4-state Turing machines, more than 9 million successfully compute n + 1. But there are some that have quite insidious bugs. An example is machine 118050142 (in the standard Wolfram Language TuringMachine numbering scheme) which “correctly” computes n + 1 for all values of n up to 62

but then suddenly at n = 63 doesn’t give 64 but instead gives 72:

Looking at all 4-state Turing machines, we can summarize where bugs occur in ones that “almost” compute n + 1:

One notable feature here is that the “highest risk” values of n for bugs are those of the form 2^{i – 1}, i.e. cases where the binary representation of n contains only 1s. It’s also perhaps notable that at least for s = 2, 3 and 4 states, the “most insidious” bug always occurs at n = 2^{2(s – 1)} – 1—and among all machines it’s very rare.

What Counts as a Bug?

To tell if a program has a bug we have to know what the program is supposed to do—or is not supposed to do. And for this we have to have some kind of precise specification. Of course the program itself provides a specification for what it will do. And with respect to this specification the program will always just “do what it does”, with no possibility of “having a bug”. But typically we imagine specifications that aren’t just the program itself, but instead have some easier-to-absorb form (e.g. the simple mathematical formula “n + 1” from the previous section). And it’s relative to specifications like these that programs can have bugs.

There are several different types of specifications that end up being used. The most direct essentially just restate the program in a different—and normally higher-level—language (say Wolfram Language vs. C++, or math notation vs. Turing machine rules). A more minimal version of this is just restating the program as a different program of the same type. Then one considers it a bug if the two programs don’t do the same thing. (For example, if a compiler optimizer changes what a program does, then it’s a bug.)

To see an example of this we can look at Turing machines again. Here are two machines that seem like they’re computing the same function

but then suddenly, at n = 27, do something different:

And indeed the pattern of where such “bugs” (i.e. differences of output) occur in this case is surprisingly complicated:

Another general type of specification is one that says not what a program should do, but rather what it should not. So, for example, with our Turing machines we could specify that we never want them to “go out of control” and start using unbounded amounts of memory (i.e. tape). Here’s an example of a Turing machine that seems like it’s just happily computing outputs:

But then suddenly, at n = 42, there’s a “bug”

and the machine goes “out of control” making a wider and wider pattern forever:

Here’s another machine, that again seems to just be happily computing outputs:

But then, for n = 151, something pathological happens—and the machine goes into an infinite loop:

We could also have a specification that says that the output from our Turing machine should always be, say, an even number. And here’s a Turing machine that seems like it’s producing only even outputs:

But then at n = 32, it suddenly gives 9!

And it always seems to be the same story: we set up a specification, and some Turing machines will precisely follow it. But we always seem to also find ones that appear to be following it—at least until they “have a bug”. In other words, it seems as if, whatever constraint we give, there’ll somehow always be machines that will insidiously escape it—in effect “having an insidious bug”.

A Cellular Automaton Example

How does what we’ve seen about “bugs” in simple Turing machines generalize? As another example, let’s look at cellular automata. And in particular, let’s look at cellular automata that are set up to “double their input” in the sense that starting with a block of n (non-white) cells, they yield 2n (non-white) cells:

As with our Turing machine examples above, there are many ways for cellular automata (say with k = 3 colors) to do the task we want—some more efficiently than others:

Sometimes it looks as if a particular rule is going to do the job—and then, suddenly there’s a “bug”—like here at n = 14:

As with our Turing machine examples, it can take a while for “bugs” to show up:

Here’s an example where the first “bug” shows up at n = 24:

And here at 32:

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

Many of the cellular automata we saw above give patterns that are simple enough that it’s “visually obvious” that they’ll “correctly double” for all input sizes:

Sometimes it’s less obvious, but it still seems fairly clear that nothing can escape a certain envelope, and so there can’t be a bug:

But what about in a case like this:

It looks awfully similar to the cases we saw above that eventually show bugs. But if we run this case up to n = 100000, no bugs appear. We can get a little more analytical, and plot the number of steps it takes for the pattern to stabilize as a function of n:

The overall trend is simple—and well fit by 7.16n steps for input n. But there are seemingly quite random fluctuations:

These fluctuations at least seem to grow roughly like . But there’s no obvious way to be sure—and to guarantee that nothing crazy will ever happen—that would lead to a bug.

What about a case like this:

Will the pattern always be “contained”, or will there eventually be a “leak” that leads to a bug? Once again we can plot the stabilization time, which again seems to increase close to linearly—and is now well fit by 9n:

There are random-looking fluctuations though:

And the question again is whether these will ever somehow “go wild”, and lead to a bug.

Well, it turns out that in this case there’s an argument we can give that this will never happen. It’d be very difficult to see this if one just looked at something like stabilization times. But it looks at the whole process of computation—which is easy to do for a cellular automaton—things become clearer.

Taking a small example we see two important features: first, the white “rind” always either stays in the same place, or moves to the left. And second, inside the rind, the pattern involves only and :

The behavior of the rind (which we can easily determine from the underlying cellular automaton rule) ensures that the complicated pattern can never expand. But could it, for example, end up becoming periodic, so that the whole pattern never stabilizes? Well, that depends on the “effective rule” inside the rind. And we can see what this is by taking the underlying cellular automaton rule

and removing all cases involving :

The answer is that it’s exactly the rule 122 elementary cellular automaton, with representing and representing . Rule 122 has the feature that when there are pairs of identical cells together, it emulates rule 90, and generates a simple nested pattern:

Analogs of that pattern show up in the original cellular automaton:

But at some point the pattern is “interrupted from the right”—and after that, the “rind” keeps on eating away at it. The only way the pattern could become periodic is for the rind to stop moving to the left, and the only way for that to happen is for the pattern within the rind to become “all ” (or all in the effective rule 122). So this then reduces to the question of whether the rule 122 pattern can ever simply die out (and become all ). But from the very structure of the rule one can see that this is impossible: as soon as there’s ever a cell, there must be cells on all subsequent steps.

So, yes, even though the patterns in this case look complicated, they must always eventually stabilize—and the underlying cellular automaton must always correctly “double its input”, with no bugs.

If the behavior of a cellular automaton is “visually simple”, we can immediately tell that it won’t show bugs. And if it’s visually complicated we can be concerned that there might be bugs. But there are still cases where—despite that complexity—the feature of behavior that we are concerned about (here, the successful doubling of any input) still always reliably happens, without any bugs.

But What about Formal Proofs?

Let’s go back to the Turing machines we discussed above. Consider a machine with the rule:

We can run it for a sequence of inputs n and see that it always seems to compute n + 1:

And indeed looking at the actual behavior of this machine it’s not too difficult to figure out that it must always compute n + 1. But can we formally prove this?

To set up a streamlined proof we need a notation that can encompass both the behavior of the Turing machine and the statements we want to make about it. And a fundamental way to get this is to represent everything using symbolic expressions (yes, as in Wolfram Language). It turns out to be convenient to represent the tape of the Turing machine like a linked list—with successive cells tied together by a (right-associative) binary operator (here ·), and with its “ends” indicated by markers (here ⊲ and ⊳):

It’s then convenient in effect to run-length encode this:

We indicate the position of the head just by giving it as part of our “linked list”, immediately following the cell that it’s on:

An example of the evolution of the Turing machine is then (where indicates what amounts to the halt state):

We can think of this particular example of Turing evolution as demonstrating that in a sense

or

And with this setup we can now specify the rules of the Turing machine in the form of “algebraic-like” axioms (where s stands for an arbitrary “subtape” and stands for a cell on the tape that can be either or :

We also need axioms to say what happens when the head reaches the right-hand end (and the machine halts):

Then we need axioms to define how our run-length encoding works:

OK, so with this setup what is it that we have to prove to show that the Turing machine always computes n + 1 when given n as input? It’s easiest to talk about two cases. First, if the binary digits of n end in 0, then the machine eventually must replace that 0 by 1. And second, if the binary digits of n end in a sequence of m 1s (indicated as ^m above) then the machine must replace this sequence by · ^m. But actually these two cases can be merged into one, and the final statement we have to prove is just (for m ≥ 0):

To prove this statement, we need to find a way to generate it from our axioms, using only valid symbolic transformations. And we can do this essentially just using the Wolfram Language FindEquationalProof:

The original axioms are indicated in green here; the theorems derived from them are blue—with the final theorem we’re trying to prove being obtained as the “output” at the bottom. In most of the proof, we’re structurally combining two theorems to derive another (either by substitution or bisubstitution ). But there’s one additional—and essential—piece: at the very end indicates the application of mathematical induction. The input to the induction is a “base case” theorem that we can call (indicated on the left), together with an assertion and a theorem that we have proved from it by the proof on the right. Mathematical induction (which we can take as a generalized axiom) then says that if we’ve shown that implies and we’ve shown then it follows that holds for all integers m.

So this means that starting from the axioms for the operation of our Turing machine, we’ve been able to prove that for all inputs n the machine correctly computes n + 1, with no bugs. By using a symbolic representation of everything, we’ve been able to reduce an essentially infinite collection of statements about all inputs n to a finite symbolic proof that applies to all n.

Among 2-state Turing machines there are 17 that correctly compute n + 1—breaking into three classes. The machine we just studied (machine 453) is an example of one of these classes. And using the method we just outlined, we can now generate proofs for all these classes (exemplified by machines 453, 445 and 1512):

So, yes, we can give formal proofs that all these machines correctly compute n + 1, with no bugs. The proofs here aren’t terribly complicated—but, after all, these particular machines are very simple in their operation. And even for 3-state machines with no bugs the proofs are still quite manageable. But if we try to go further, then, as we’ll discuss later, we’ll inevitably run into arbitrarily long proofs. (And, by the way, if we try to make proofs for the cellular automaton programs we discussed above, this seems to happen in any case that isn’t visually obvious.)

It’s worth mentioning that the proofs we’re showing are just particular ones found by FindEquationalProof. They aren’t unique, and they might not be as simple as they could be. But they still give a good indication of what kinds of symbolic proofs are possible for Turing machines.

So what happens if we try to produce a proof for a machine that has a bug? To see that, we have to talk about how we construct proofs like the ones above. The basic idea is to start from the axioms and then try to find a way to string them together to get to the theorem we want. In essence we’re forming a multiway graph of possible theorems—then our proof corresponds to what amounts to a path-like subgraph in this graph.

Here’s how the multiway graph starts—with the original axioms on top:

And if we continue for a few more steps (and visually rearrange the graph) we find that we can “fish out” of this multiway graph exactly our proof for this case above:

OK, so what about a machine with a bug—like the very first example we used above? The beginning of the multiway graph for this machine looks similar to the one before:

But now—however far we go—we never find a proof

because, in fact, the result we’re trying to prove isn’t true, so there isn’t a proof. And we know that because, if we test sufficiently many cases of the Turing machine, we can explicitly find the bug.

And in the end, we don’t get any fundamental advantage by trying to make a proof rather than just running the Turing machine. In both cases we have to expend a potentially unbounded amount of computational effort. It’s just a choice between putting that effort rather directly into enumerating and running cases of the Turing machine, or instead putting the effort into building up the multiway graph to try and find a proof in it.

We can think of the style of proof that we’ve used so far as being based on equational logic, and in effect building up by structural substitution (and induction) the theorems we want from the axioms we’ve provided. An alternative approach is to use type theory (as proof assistants like Lean do), and instead to build up a representation of a type, then to prove that this type is possible by giving an example of something that has that type. In our case here, the type we want to prove is “inhabited” is basically a statement of the theorem that for all n our Turing machine computes n + 1. Using an LLM able to validate steps by calling a proof assistant, we can eventually generate a proof for our machine 445 example from above. And although it’s not terribly illuminating, we can give a visual representation of the proof:

Computational Irreducibility and Bugs

We’ve now seen several minimal examples of what we can think of as “bugs”: unexpected things even very simple programs can do. But what is the fundamental source of these “unexpected things”?

Ultimately it’s computational irreducibility—and our inability to know in general what a program will do except in effect by explicitly running it. And what’s critical is that computational irreducibility is not just something that’s in principle possible; it’s something that (according to the Principle of Computational Equivalence) is at some level ubiquitous—and affects essentially any system whose behavior is not obviously simple.

When computational irreducibility is present, it means that the behavior of a system can in general only be predicted by an irreducible amount of computational work. So that means that with a bounded amount of computational work it’s always possible for the system to surprise us—and in particular for the system to unexpectedly exhibit what we consider to be a bug.

Whether a system has any bugs is at some level an infinite question. In general, you might have to check its outputs from all its infinite number of possible inputs—and you might not even know in any particular case whether the system would halt and give an output at all. And indeed it’s been known for a century that such infinite questions about computational systems can in principle be undecidable. But the point is that this isn’t just a problem in principle; it’s a problem in practice, that affects a wide range of even very simple programs.

But, one might ask, why not just use programs that don’t have these problems? Programs where you can foresee their behavior, and be sure they have no bugs. Well, here’s the issue: if you can completely foresee what a program will do, what’s the point of running it? Why not, in effect, just immediately “write down the answer”, without ever having to run the program? In other words, to make the program worth actually running, there have to be parts of its behavior you can’t foresee. But then there’s a piece of intuition from the Principle of Computational Equivalence: once there’s anything you can’t foresee, there tends to be a lot you can’t foresee. In other words, the system will tend to be full of computational irreducibility.

Computational irreducibility is in a sense what makes computation powerful. But it’s also what makes it unpredictable. And in practice—intentionally or not—it’s very common for programs to have what amounts to a “spark of computational irreducibility inside” that’s somehow kept controlled enough to do what one wants.

Maybe it’s OK for a program to do wild things—so long as it satisfies at least some property (like not going into an infinite loop). Maybe there’s some particular property one wants the program to have. One important feature of computational irreducibility is that whenever it’s present, there must also be pockets of computational reducibility present. In other words, even though computational irreducibility says one can’t predict everything about what a system will do, there will always be certain things about a system that one will be able to predict. And if among those things there are ones that align with the properties one wants, then one may be able to know that the system will “exhibit no bugs”, at least with respect to these properties.

We saw above in the case of some simple Turing machines how symbolic proofs can be constructed so that certain programs do certain things, and thus don’t have certain kinds of bugs. So how does this relate to computational irreducibility? One can think of proofs as taking advantage of pockets of computational reducibility, to provide finite summaries of infinite things. But there’s no (static) finite summary that can be given of everything a computationally irreducible system does. And proofs about a computationally irreducible process will inevitably get longer and longer as one tries to talk about more and more steps in the process.

It can be a confusing situation. One studies a program and discovers all sorts of facts about its operation (“this never does that”; “this remains constant”; etc.). And one might think that with enough such facts one would be able to guarantee that there won’t be bugs. But if there’s computational irreducibility one would in effect need an infinite number of facts to do that. And in practice it may or may not be that some particular property one’s focusing on will be “guaranteed bug free” by the facts one’s established.

Did I Test Enough Cases? The Failure of Ruliological Induction

Scientific induction is a cornerstone of natural science. You see something in the world happen a certain way enough times, and you assume it’ll always happen that way (and that there’s a “scientific law” about it). But what about in ruliology? Can we apply scientific induction there? You test a lot of Turing machines. You observe a certain pattern of behavior. Will the pattern always be there? Scientific induction would say yes. But if there’s a “bug” it won’t be. And the point is that in ruliology—courtesy of computational irreducibility—there’s always the potential for surprises, and for “bugs” that violate whatever laws we might have inferred.

Particularly given that from what we know now, it seems that what’s underneath is so computational, one might wonder why scientific induction would ever have worked in the first place. The answer has to do with the fundamental nature of natural science and scientific laws. At some level what science is trying to do is to take what happens in the world, and explain at least certain aspects of it with “narratives” that our minds can grasp. And the point is that such narratives—almost by definition—rely on pockets of computational reducibility. What’s underneath may involve all sorts of computational irreducibility. But that’s not what we concentrate on when we want to “do science”. We look for computationally reducible regularities that we can “summarize” with our scientific laws and our narratives.

Realistically, this works better in some places than others. Physics has been a big success story. Biology not. In our Physics Project we can see that there’s lots of computational irreducibility. It’s just that the physical laws relevant for observers like us manage to largely avoid it. In biology there’s again computational irreducibility—indeed it seems to be essential for life to be able to do what it does. And now if we want to “look inside”—and for example do medicine—we’re forced to confront computational irreducibility. Which shows up as ubiquitous failures of reproducibility in our experiments, and, in effect, a failure of scientific induction. (One can try to save scientific induction by talking about probabilities not certainties, but eventually one always has to confront computational irreducibility.)

But what about with programs? Well, insofar as the details of what programs do matters, one’s going to have the potential to run into computational irreducibility. And, as we discussed above, we’ll only avoid that if whatever we’re looking at is just a pocket of reducibility, and not looking at the “whole spectrum of behavior”.

OK, but so let’s say we’re trying to test a program by looking at lots of specific cases. How do we know if we’re “stuck in a pocket of reducibility”, or are actually seeing the whole “spectrum of behavior”, bugs and all? A typical approach in practice is to randomly sample possible inputs (or to introduce random “fuzz” around known inputs). Will this work? Well, it depends on “how good” the “randomness” is, and what the distribution—and density—of bugs is.

Say our “randomness” came from a numerical algorithm where only certain kinds of sequences of successive numbers could occur. The program we’re testing might not show “bugs” in these cases, only in others. And in general there’s a kind of competition between the randomness and the program. Is the program “computationally strong enough” to “decode” the randomness, and do something special in those cases? Or will the randomness sample the behavior of the program in a way that at least doesn’t systematically avoid its “bugs”?

Of course, even if the sampling doesn’t “systematically avoid” bugs, it might just not hit them, because the bugs exist only in some “special corner” of possible inputs. But if the randomness is “computationally strong enough” there won’t be any “special corners” that can “hide” from it.

Still, the number of samples might just not be large enough to ever hit a bug—given the density of bugs that are present. (If one assumes a certain uniformity and independence one can use simple probabilistic arguments to compute how probabilities for hitting bugs would increase if one were to take more samples.)

So what density of bugs do we expect? Well, we’ll presumably not call something a “bug” unless it’s rare. But in the world of programs, how rare can things be? The answer is: as rare as one can imagine. It’s very much like the “busy beaver” problem of what the longest finite lifetime for a particular class of programs can be. In that case, it’s the finite lifetime that’s unbounded. Here it’s the smallness of the probability of a “bug”. (A Turing machine with the “hardest-to-find bug” one might whimsically call a wily weasel machine.)

But what happens in practice? Well, at least in doing ruliology my consistent experience has been that rare phenomena show up all the time. It’s extremely common to sample many instances of some type of system and see some consistent behavior. And there’s then a considerable tendency to use scientific induction to conclude that this behavior must always occur. But with great regularity, if one takes more samples—and particularly if one samples exhaustively—there’s a surprise. Sometimes one needs to look at thousands, sometimes millions, sometimes billions and sometimes trillions of cases. But then one sees something unexpected, that—relative to how one thought the system would behave—one can think of as a “bug”.

Some Typical Ruliological Surprises

The computational universe is full of surprises. And in my (nearly) half century of exploring it with ruliology, I’ve seen a very large number of them. In fact, in my experience it’s very rare to do ruliology and not have surprises. In some ways it’s a humbling experience—if also an inspiring one. You imagine you know how things are going to work. And then the unexpected happens. And you realize that the computational universe is just so much richer than you ever imagined.

One of my very early—and very significant—ruliological surprises had to do with the simplest cellular automata. Enumerating possible (quiescent) rules, they all seemed to do very regular things. But then, quite unexpectedly, there was rule 30, with all its complexity:

For Turing machines, it’s a similar story—though one has to go further to find a big surprise. And now it’s (2-state, 3-color) machine 596440 that finally does something surprising and complex:

What about surprises just from changing “inputs” (like in our earlier discussions above)? As an example, consider the 3-color totalistic code 1329 cellular automaton. For many inputs (i.e. initial conditions), it does a small range of things:

But then at initial condition 916 something different suddenly happens:

Keep going further and there’s another surprise—a pattern that gets bigger and bigger:

And then, suddenly, with input 97,439, there’s something one would never have guessed this rule could do:

It’s very common to be looking at some system and wondering what it will “do in the end”, if you run it long enough. Will it halt, for example, or just keep going forever? The phenomenon of computational irreducibility says it can in principle be arbitrarily hard to tell, but the remarkable thing is how often in practice it’s hard to tell. As a somewhat extreme example, consider the standard evaluation of the combinator expression s[s[s]][s][s][s][s[s][k[k]]]. After 1000 steps it seems like it’s continuing to produce larger and larger outputs:

At 100,000 steps one can see things are bouncing around, but there’s no evidence anything is going to halt:

But then, suddenly, after no less than 137,356,329 steps, it does in fact halt:

Here’s an example of a slightly different kind. If you run the 2D cellular automaton (outer totalistic 9-neighbor code 746, starting from ) it seems like it’s producing a roughly circular pattern (albeit it with about 4% anisotropy)

But then, suddenly, after about 3000 steps, the pattern sprouts a “beak” that breaks the circularity:

As another kind of example, consider a system where there are many possible moves—that one can represent with a multiway graph. In this we’re successively adding a single black cell in all possible ways, with the constraint that the cell always has to have exactly 2 neighbors (out of 8) that are already black. The first few steps in the multiway graph of “possible histories” for such a system are:

And from this graph one might assume that the growth would always keep going. But continuing further with the multiway graph, there’s a surprise: a particular cluster produced after 9 steps that simply can’t be grown:

It’s a bit like what might happen in a puzzle or a game: there’s a thin set of moves that lead one to a special outcome—here a halting state:

In a sense, ruliology is a field where “bugs” are the rule, not the exception. And in fact, the ubiquity of computational irreducibility in the computational universe make it essentially inevitable that it’ll be very common for there to be “surprises” that break our expectations, and that we might call “bugs”.

Mathematical “Bugs”

If “bugs” are so common in ruliology, what about in mathematics? Let’s say one’s studying some mathematical system, and one’s found lots of examples that work a certain way. One might form a hypothesis that things will always work that way. And perhaps they really do. Or perhaps instead, somewhere out there is a counterexample—in effect a bug in one’s hypothesis.

Let’s say you’re looking at factors of polynomials of the form xⁿ – 1:

You try many cases. All of them seem to give results with coefficients ±1. But then you try x^{105 – 1}. And suddenly there’s something different—a coefficient of 2:

Here’s another example. Look at the cumulative difference in the number of primes of the form 3m + 2 and 3m + 1. Plotting the result for the first 100,000 primes it seems like this difference will always be positive:

But it doesn’t go on that way. At the 23338590792^th prime it flips around, and becomes negative.

There are lots of results like this, particularly involving primes, number theory, etc.—and indeed for some of them one has to go astronomically far to find the first known “bugs”.

But somehow in the mainstream of pure mathematics, such issues are not very common. And in a sense this seems to reflect something about the fundamental nature of the activity we call mathematics.

We know from Gödel’s theorem that questions—even, say, about arithmetic equations involving integers—can be equivalent to arbitrary computations, and therefore are in principle exposed to all the phenomena we see in ruliology. But—as I’ve discussed at length elsewhere—pure mathematics as it’s normally practiced tends to concentrate on what amount to more “human-level” questions, that in effect exist in pockets of computational reducibility, that avoid the generic computational irreducibility of ruliology.

And indeed it’s this that makes it reasonable to expect that mathematics we’re interested in can be nailed down with proofs of manageable length. And if we get to the point of having a fully formalized symbolic proof, then it’s typically easy to check. Of course, just like with program verification, the link from what we think we’re trying to say to that formalization can again have bugs. In the actual practice of pure mathematics, though, these things are less important than one might imagine. Because the core of pure mathematics is just not so much the details of proofs as about the creation of abstract structures that provide frameworks for human mathematical understanding.

But what does it really mean that mathematics doesn’t run into ruliology-style bugs all the time? In a sense it’s a direct reflection of the fact that the development of pure mathematics has at every stage emphasized human understanding. If the goal is just to find out what’s true about the structures considered in mathematics, there’s a different—and powerful—approach one can take: experimental mathematics. And indeed serious experimental mathematics is methodologically just like ruliology, albeit operating on the constructs of mathematics rather than just pure rules and programs. And, like ruliology, experimental mathematics is directly exposed to computational irreducibility—with all the surprises and “bugs” that brings.

Bugs in Practice

So let’s say you want to create a program that doesn’t have bugs. How should you do it? 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 you wanted.

But, OK, so at some level you’re going to have to gloss over certain things your program is doing. So what then gives you the best chance to have the program do what you want? Language design, I believe, is key. Because language design is all about providing primitives that do what we humans want, and that we can understand.

There are an infinite number of programs one can write. Each will do something. But with overwhelming probability the things they do will not be anything we humans want. What a well-designed language does is to provide as primitives lumps of computational work that are things humans typically actually want. They define, in a sense, a framework for the successful computational formalization of human thought.

And what this means is that if you write your program in a sufficiently well-designed language, the structure of the language itself will lead you towards making your program be one that does what you want—without what you’d consider bugs. Well, it so happens that I’ve spent the better part of the past many decades trying to make the Wolfram Language be a language that achieves these things.

And indeed in Wolfram Language it’s possible to express what are ultimately remarkably complex tasks with remarkably small, simple and “understandable” programs. In effect, what’s happened is that most of the computational irreducibility has been packed into the primitives of the language, so that what’s left over is the part that’s accessible to us humans, and that maps into our natural patterns of thinking.

I’ve seen it over and over again: in Wolfram Language it’s the short program that’s the one that does what you want, without what you consider bugs. If there’s extra complexity in the program, it’ll probably introduce what you’ll consider bugs. In other words, in the space of all possible programs, the ones we as humans tend to want are those that can be expressed as short programs in Wolfram Language.

But however well designed your language is, any time you write a program that actually needs to be written (in the sense that it’s achieving at least some irreducible computation), it’ll have the possibility of doing something you didn’t expect or foresee—and that you might consider a bug.

So what can you do about that? My lifelong experience is that in practice the most important thing is to try to “see inside” what the program is doing, in as complete but human accessible a way as possible. In our examples of cellular automata above, visualizing the whole pattern was crucial. And indeed in many cases basic human visual perception was enough to give one complete confidence that the system would always “do the right thing”. Building on this “visual understanding” one could no doubt (typically with some effort) construct a formal “correctness theorem”. But to do that purely from a description of the system—without first “actually seeing what it does inside” —would run into issues of computational irreducibility and typically be immeasurably more difficult.

But how does one in general “see inside” a computation? 1D cellular automata are a particular easy case in which the process of computation plays out in a “spacetime array” that can immediately be presented as an image accessible to our powers of visual perception. 1D Turing machines are more or less the same way, particularly if one (carefully, so as not to lose important information) compresses their spacetime behavior. For other kinds of systems that don’t have such an immediate “spacetime” presentation things can be more complicated, and there is a certain art in visualizing the behavior of such systems well.

In traditional software, things can be even more complicated. Visualizing detailed telemetry from inside a running program can often be revealing. But there tends to be no real way to “pull out parts of a program separately”—because there’s complicated shared state encoded in values of variables, etc. And this is one of the great strengths of the symbolic paradigm that’s so deeply embodied in the Wolfram Language. Because within this paradigm, even tiny fragments of programs can be run on their own, giving one at least the raw material to “see in detail what a program is doing”.

When programs have bugs one question to ask is “how did those bugs get in there?” Very often in practice they are the result of simple human foibles (off-by-one errors, failure to see some dependency, etc.) Sometimes things like typechecking constrain things to a point where at least the most obvious errors are immediately caught (albeit at the cost of less flexibility for the programmers). And modern AIs are typically quite good at finding bugs that follow the patterns of typical human missteps.

What we’ve mostly discussed here are, however, what amount to deeper kinds of bugs. They are bugs that do not follow any human-related patterns. They are, in a sense, bugs that arise from the very nature of computation itself. Yes, they could in practice be put there by a human or AI programmer. But they’d also be something that could show up even if a program were constructed by exhaustive search—or adaptive evolution—with some finite set of constraints. (One might imagine that in a situation like this, one could just make the “constraint” be a “proof of correctness”. But as we discussed above, being able to construct a complete such proof is essentially incompatible with the program achieving anything that is “computationally significant”.)

While one might not think of them as traditional “programs” one might wonder about modern AIs and things like neural nets that have been trained from examples. The expectations are certainly much lower there: one does not expect specific, precise (or even, often, repeatable) output—though particularly when there’s iterative improvement one may get to the point where a constraint may (at least with high probability) be exactly satisfied.

But ultimately (a bit like the situation with trained wild animals) I don’t think one can expect to be sure of anything. Yes, the process of machine learning can put together “lumps of irreducible computation” in a way that seems to satisfy the constraints and training objectives one’s defined. With overwhelming probability what gets constructed is not an “understandable mechanism”. And inevitably then it’s always possible for some piece of computational irreducibility to “spurt out”, and for the system to behave in a way you don’t expect. What actually happens in a realistic neural net will be very hard to visualize or to “understand at a human level”. And indeed the core of what’s going on will basically be like what we’ve seen here even in the very simple systems we’ve studied.

But what if we were to allow some bugs? If our program is written in a language whose primitives are a good fit to what we want to compute, then allowing bugs is not likely, for example, to let the program be any shorter. But if our program is written at a lower level, say as a Turing machine, then we can expect (as we saw above) that allowing some bugs can allow the program to be shorter. In such a case we can think of ourselves as trying to “harness raw computation”, and it’ll tend be easier to find a “lump of computation” that approximately fits what we’re trying to do than one that exactly does.

So let’s say we’re running a program that we think will operate in a certain way. But it doesn’t. And instead it has what we can consider a bug. Well, if we’re trying to do engineering we’d consider this a failure. But if we’re doing science, we might consider it a success. Because in effect we’ve discovered something we didn’t expect. And indeed we can think of much of the progress of ruliology as being precisely about the discovery of a long sequence of “bugs”—or at least bugs relative to our normal intuition about how things work. But now, with what we learn from ruliology, we can turn this around and start to understand some of the foundations of the ubiquitous and fundamental phenomenon of bugs, wherever they may be found.

Thanks

I’d like to thank several members of the Wolfram Institute for their help: Richard Assar, Júlia Campolim, Nik Murzin and Willem Nielsen. I’d also like to thank the Wolfram Software Quality Assurance team, who, over the past four decades have handled more than half a million bugs (of which the vast majority are now fixed!), and whose work has helped me develop my intuition for the phenomenon of bugs. Thanks also to all those who’ve worked with me on ruliology over the years—and who’ve witnessed my repeated reaction to ruliological surprises: “We’ve just got to recognize that the computational animals are smarter than we are!”