My All-Time Favorite Science Discovery

June 1, 1984—forty years ago today—is when it would be fair to say I made my all-time favorite science discovery. Like with basically all significant science discoveries (despite the way histories often present them) it didn’t happen without several long years of buildup. But June 1, 1984, was when I finally had my “aha” moment—even though in retrospect the discovery had actually been hiding in plain sight for more than two years.

My diary from 1984 has a cryptic note that shows what happened on June 1, 1984:

There’s a part that says “BA 9 pm → LDN”, recording the fact that at 9pm that day I took a (British Airways) flight to London (from New York; I lived in Princeton at that time). “Sent vega monitor → SUN” indicates that I had sent the broken display of a computer I called “vega” to Sun Microsystems. But what’s important for our purposes here is the little “side” note:
Take C10 pict.
R30
R110

What did that mean? C10, R30 and R110 were my shorthand designations for particular, very simple programs of types I’d been studying: “code 10”, “rule 30” and “rule 110”. And my note reminded me that I wanted to take pictures of those programs with me that evening, making them on the laser printer I’d just got (laser printers were rare and expensive devices at the time).

I’d actually made (and even published) pictures of all these programs before, but at least for rule 30 and rule 110 those pictures were very low resolution:

But on June 1, 1984, my picture was much better:

For several years I’d been studying the question of “where complexity comes from”, for example in nature. I’d realized there was something very computational about it (and that had even led me to the concept of computational irreducibility—a term I coined just a few days before June 1, 1984). But somehow I had imagined that “true complexity” must come from something already complex or at least random. Yet here in this picture, plain as anything, complexity was just being “created”, basically from nothing. And all it took was following a very simple rule, starting from a single black cell.

Our usual intuition that to make something complex required “complex effort” was, I realized, simply wrong. In the computational universe one needed a new intuition. And the picture of rule 30 I generated that day was what finally made me understand that. Still, although I hadn’t internalized it before, several years of work had prepared me for this. And just days later I was at a conference already talking confidently about the implications of what I’d seen in rule 30.

Over the years that followed, rule 30 became basically the face of the phenomenon I had discovered. By 1985 I devoted a whole paper to it, in A New Kind of Science it was my initial and quintessential example, for the past quarter century a picture of rule 30 has adorned my personal business cards, and in 2019 we launched the Rule 30 Prizes to promote the rich basic science of rule 30:

But what about “C10”—the first item in my cryptic note? What was that? And what became of it?

First Sightings of Code 10

Well, C10 was “code 10”, or, more fully, “k = 2, r = 2 totalistic code 10 cellular automaton”. (I used the term “code” as a way to indicate a totalistic, rather than general, “rule”.) And, actually, I had looked at code 10 several times before, never really paying much attention to it.

The first explicit mention I find in my archives is from February 1983 (apparently reporting on something I’d done in January of that year). I had been doing all sorts of computer experiments on cellular automata, recording the results in a lab notebook. One page has observations about what I then called “summational rules” (I would soon rename these “totalistic”). And there’s code 10:

Mostly I had been studying the behavior starting from random initial conditions, but for code 10 I noted: “very irregular, even from simple initial state”. Within a couple of months I had even made (on an electrostatic printer) a high-resolution picture of code 10 starting from a single black cell—and here it is, prepared for publication, Scotch tape and all:

It appeared in a paper I wrote in May 1983. But the paper (entitled “Universality and Complexity in Cellular Automata”) was mostly about other things (for example, introducing my four general classes of cellular automaton behavior and talking quite a lot about code 20 as an example of class 4 rule), and it contained only a passing comment about code 10:

Code 10 is a range-2 rule, which means that the patterns it generates can grow by 2 cells on each side at each step. And the result is that the patterns quickly get quite wide, so that if one cuts them off when they “hit the edge of the page” (as my early programs “conveniently” tended to do) they don’t go very far, and one doesn’t get to see much of code 10’s behavior.

And it was this piece of “ergonomics” that caused me to basically ignore code 10—and not to recognize the “rule 30 phenomenon” until I happened to produce that high-resolution image of rule 30 on June 1, 1984.

I didn’t entirely forget code 10, for example mentioning it in a note to “Why These Discoveries Were Not Made Before” in my 2002 book A New Kind of Science:

But now that forty years have passed since I made—and basically ignored—that “C10” picture, I thought it would be nice to go back and see what I missed, and to use our modern Wolfram Language tools to spend a few hours checking out the story of code 10.

It’s an exercise in what I now call “ruliology”—the basic science of studying what simple rules do. And whenever one does ruliology there are certain standard things one can look at—that I showed many examples of in A New Kind of Science. But in a quintessential reflection of computational irreducibility there are also always “surprises”, and special phenomena one did not expect. And so it is with code 10.

Code 10: The Basic Story

Code 10 is a cellular automaton operating on a line of black and white cells, at each step adding up the values of the 5 cells up to distance 2 from any given cell (black is 1, white is 0). If the total is 1 or 3, the cell is black on the next step; otherwise it’s white (in base 2 the number 10 is 001010):

And, yes, in many ways this rule is even simpler to describe—at least in words—than rule 30. And if one thinks of it in terms of Boolean expressions, it can also be written in a very simple form:

(By the way, as a general k = 2, r = 2 rule, code 10 is rule 376007062.)

So what does code 10 do? Here are a few steps of its evolution starting from a single black cell:

And here are 2000 steps:

And, yes, even though it’s a simple rule, its behavior looks highly complex, and in many ways quite random. One immediate observation is that—unlike rule 30—code 10 is symmetric, so the pattern it generates is left-right symmetric. The center column isn’t interesting: after having black cells for 2 steps, it’s white thereafter. (And by substituting values yx0xy into the Boolean expression above, it’s easy to prove this.)

Filling the white region around the center column with red we get:

There doesn’t seem to be any long-range regularity to the way the width of this region changes:

And indeed the (even) widths seem at least close to exponentially distributed:

What if one goes one column to the left or right of the center? Here’s the beginning of the sequence one gets:

And, yes, every other cell is white. Picking only “even-numbered positions” we get:

Looking at the accumulated mean for 100,000 steps suggests that this sequence isn’t “uniformly random”, and that slightly fewer than 50% of the cells end up being black:

Going away from the center line, every other column has white cells every two steps. Sampling the pattern only at “odd positions” in both “space and time” we get a pattern that looks similar—though not identical—to our original one:

Looking at every cell, the overall density of the pattern seems to approach about 0.361. Looking only at “odd positions” the overall density seems to be about 0.49. And, yes, the fact that it doesn’t seem to become exactly 1/2 is one of those typical “not-quite-as-expected” things that one routinely finds in doing ruliology.

There are some aspects of the code 10 pattern, though, that inevitably work in particular ways. For example, if we “rotate” the pattern so that its boundary is vertical, we can see that close to the boundary the pattern is periodic:

The period progressively doubles at depths separated by 1, 1, 4, 6, 8, 14, 124, …—yielding what may perhaps ultimately be a logarithmic growth of period with depth:

Other Initial Conditions, and a Surprise

We’ve looked at what happens with an initial condition consisting of a single black cell. But what about other initial conditions? Here are a few examples:

We might have thought that the “strength of randomness” would be large enough that we’d get patterns that look basically the same in all cases. But so what’s going on in the case? Running twice and five times as long reveals it’s actually nothing special; there just happen to be a few large triangles near the top:

So will nothing else notable happen with larger initial conditions?

What about ? Let’s run that a little longer:

And OMG! It’s not random and unpredictable at all. It’s a nested pattern!

Even in the midst of all that randomness and computational irreducibility, here is a dash of computational reducibility—and a reminder that there are always pockets of reducibility to be found in any computationally irreducible system, though there’s no guarantee how difficult they will be to find in any given case.

The particular nested pattern we get here is a bit like the one from the additive elementary rule 150, that simply computes the total mod 2 of the three cells in each neighborhood:

And it turns out to be almost exactly the r = 2 analog of this—the additive rule (code 42) that takes the total mod 2 of the five cells in the r = 2 neighborhood:

The limiting fractal dimension of this pattern is:

Is unique, or does this same phenomenon happen with other “seeds”? It turns out to happen again for:

So what’s going on here? Comparing the detailed pattern in the code 10 case with the additive rule case, there’s no immediate obvious correspondence:

But if we look at the rules for code 10 and code 42 respectively:

We notice that there’s really only one difference. In code 10, gives while in code 42, it gives . In other words, if code 10 avoids ever generating any block, it will inevitably behave just like code 42—and shows nested before. And that’s what happens for the initial conditions above; they can for example lead to blocks, but never .

Another notable and at first unexpected phenomenon concerns the overall density of black cells in patterns from different initial conditions:

And what we find is that for even-length initial blocks the density is about 0.47, while for odd ones it’s about 0.36. At first it might seem very strange that something as global as overall density could be affected by the initial conditions. But once again, it’s a story of what blocks can occur: in the odd-length case, there’s a checkerboard of guaranteed-white cells, which just doesn’t exist in the even-length case.

Other Things to Study

We’ve been looking at what code 10 does with specific, simple initial conditions. What about with random initial conditions? Well, it’s not terribly exciting. It basically just looks random all the way through—which, by the way, is part of the reason I didn’t pay much attention to code 10 back in 1983:

But even though this looks quite random, it’s for example not the case that every single possible block of values can occur. Though it’s very close. Let’s say we start from all possible sequences of 0s and 1s in the initial conditions. Then—using methods I developed in 1984 based on finite automata—it’s possible to determine that even after 1 step there are some blocks of values that can’t occur. But it turns out that one has to go all the way to blocks of length 36 before one finds an example:

Although the patterns generated by code 10 generally look quite random, if we look closely we can see at least patches that are fairly regular. The most obvious examples are white triangles. But there are other examples, most notably associated with regions consisting of repetitions of blocks with periodic behavior:

Complementary to this is the question of what code 10 does in regions of limited size—say with cyclic boundary conditions, starting from a single black cell. The result is quite different for regions of different sizes:

For a region of size n, a symmetric rule like code 10 must repeat with a period of at most 2^n/2. Here are the actual repetition periods as a function of size, shown on a log plot:

These are results specifically for the single-cell initial condition. We can also generate state transition diagrams for all 2ⁿ possible states in a size n code 10 system:

And mostly what we see is highly contractive behavior, with many different initial states evolving to the same final state—even though “eventually” we should start seeing larger cycles of the kind we picked up above when we looked at evolution from a single-cell initial condition.

And, yes, I could go on, for example repeating analyses I’ve done in the past for rule 30. A lot of what we’d see would be at least qualitatively much the same as for rule 30—and essentially the result of the appearance of computational irreducibility in both cases. But it’s a feature of the computational universe—and indeed one of the many consequences of computational irreducibility—that different computational systems will inevitably have different “idiosyncrasies”. And so it is for rule 30 and code 10. Rule 30 has an “Xor on one side” which gives it special surjectivity properties. Code 10 on the other hand has its block emulations, which lead, for example, to the surprise of nesting.

I’ve now spent many years studying the ruliology of simple programs, and if there’s one thing that still amazes me after all that time it’s that there are always surprises. Even with very simple underlying rules one can never be sure what will happen; there’s no choice but to just do the experiments and see. And, in my experience, pretty much whenever one thinks one’s “got to the end” and “seen everything there is to see”, something completely unexpected will pop out—a reminder that, as the Principle of Computational Equivalence tells us, these simple computational systems are in some sense a microcosm of everything that’s possible.

Ruliology is in many ways the ultimate foundational science—a science concerned with pure abstract rules not set up with any particular reference either to nature or to human choice. In a sense ruliology is our best path to ultimate pure abstraction—and unfettered exploration of the ruliad. And at least for me, it’s also something very satisfying to do. These days, with modern Wolfram Language, it’s all very streamlined and fast. Sitting at one’s computer, one can immediately start visiting vast uncharted areas of the computational universe, seeing things—and often very beautiful things—that have never been seen before, and discovering new but everlasting things anchored in the bedrock of computation and of simple programs.

It’s been fun spending a few hours studying the ruliology of code 10. Essentially everything I’ve done here I could have done (though not nearly as efficiently) back in 1983 when I first came up with code 10. But as it was, code 10 in a sense had to “wait patiently” for someone to come and look at it. The form of the rule 30 pattern is in some ways more “human-scaled” than code 10. But, as we’ve seen here, code 10 still manifests the same core phenomenon as rule 30. And now, forty years after printing that “C10” picture, I’m happy to be able to say that I think I’ve finally gotten at least a passing acquaintance with another remarkable “computational world” out there in the computational universe: the world of code 10.

The Model

Why does biological evolution work? And, for that matter, why does machine learning work? Both are examples of adaptive processes that surprise us with what they manage to achieve. So what’s the essence of what’s going on? I’m going to concentrate here on biological evolution, though much of what I’ll discuss is also relevant to machine learning—but I’ll plan to explore that in more detail elsewhere.

OK, so what is an appropriate minimal model for biology? My core idea here is to think of biological organisms as computational systems that develop by following simple underlying rules. These underlying rules in effect correspond to the genotype of the organism; the result of running them is in effect its phenotype. Cellular automata provide a convenient example of this kind of setup. Here’s an example involving cells with 3 possible colors; the rules are shown on the left, and the behavior they generate is shown on the right:

We’re starting from a single () cell, and we see that from this “seed” a structure is grown—which in this case dies out after 51 steps. And in a sense it’s already remarkable that we can generate a structure that neither goes on forever nor dies out quickly—but instead manages to live (in this case) for exactly 51 steps.

But let’s say we start from the trivial (“null”) rule that makes any pattern die out immediately. Can we end up “adaptively evolving” to the rule above? Imagine making a sequence of randomly chosen “point mutations”—each changing just one outcome in the rule, as in:

Then suppose that at each step—in a minimal analog of natural selection—we “accept” any mutation that makes the lifetime longer (though not infinite), or at least the same as before, and we reject any mutation that makes the lifetime shorter, or infinite. It turns out that with this procedure we can indeed “adaptively evolve” to the rule above (where here we’re showing only “waypoints” of progressively greater lifetime):

Different sequences of random mutations give different sequences of rules. But the remarkable fact is that in almost all cases it’s possible to “make progress”—and routinely reach rules that give long-lived patterns (here with lifetimes 107, 162 and 723) with elaborate morphological structure:

Is it “obvious” that our simple process of adaptive evolution will be able to successfully “wrangle” things to achieve this? No. But the fact that it can seems to be at the heart of why biological evolution manages to work.

Looking at the sequences of pictures above we see that there are often in effect “different mechanisms” for producing long lifetimes that emerge in different sequences of rules. Typically we first see the mechanism in simple form, then as the adaptive process continues, the mechanism gets progressively more developed, elaborated and built on—not unlike what we often appear to see in the fossil record of biological evolution.

But let’s drill down and look in a little more detail at what’s happening in the simple model we’re using. In the 3-color nearest-neighbor (k = 3, r = 1) cellular automata we’re considering, there are 26 (= 3³ – 1) relevant cases in the rule (there’d be 27 if we didn’t insist that
). “Point mutations” affect a single case, changing it to one of two (= 3 – 1) possible alternative outcomes—so that there are altogether 52 (= 26 × 2) possible distinct “point mutations” that can be made to a given rule.

For example, starting from the rule

the results of possible single point mutations are:

And even with such point mutations there’s usually considerable diversity in the behavior they generate:

In quite a few cases the pattern generated is exactly the same as the one for the original rule. In other cases it dies out more quickly—or it doesn’t die out at all (either becoming periodic, or growing forever). And in this particular example, in just one case it achieves “higher fitness”, surviving longer.

If we make a sequence of random mutations, many will produce shorter-lived or infinite lifetime (“tumor”) patterns, and these we’ll reject (or, in biological terms, we can imagine they’re “selected out”):

But still there can be many “neutral mutations” that don’t change the final pattern (or at least give a pattern of the same length). And at first we might think that these don’t achieve anything. But actually they’re critical in allowing single point mutations to build up to larger mutations that can eventually give longer-lived patterns:

Tracing our whole adaptive evolution process above, the total number of point mutations involved in getting from one (increasingly long-lived) “fitness waypoint” to another is:

Here are the underlying rules associated with these fitness waypoints (where the numbers count cumulative “accepted mutations”, ignoring ones that go “back and forth”):

One way to get a sense of what’s going on is to take the whole sequence of (“accepted”) rules in the adaptive evolution process, and plot them in a dimension-reduced rendering of the (27-dimensional) rule space:

There are periods when there’s a lot of “wandering around” going on, with many mutations needed to “make progress”. And there are other periods when things go much faster, and fewer mutations are needed.

As another way to see what’s going on, we can plot the maximum lifetime achieved so far against the total number of mutation steps made:

We see plateaus (including an extremely long one) in which “no progress” is made, punctuated by sometimes-quite-large, sudden changes, often brought on by just a single mutation.

If we include “rejected mutations” we see that there’s a lot of activity going on even in the plateaus; it just doesn’t manage to make progress (one can think of each red dot that lies below a plateau as being like a mutation—or an organism—that “doesn’t make it”, and is selected out):

It’s worth noting that there can be multiple different (“phenotype”) patterns that occur across a plateau. Here’s what one sees in the particular example we’re considering:

But even between these “phenotypically different” cases, there can be many “genotypically different” rules. And in a sense this isn’t surprising, because usually only parts of the underlying rule are “coding”; other parts are “noncoding”, in the sense that they’re not sampled during the generation of the pattern from that rule.

And for example this highlights for each “fitness waypoint rule” which cells make use of a “fresh” case in the rule that hasn’t so far been sampled during the generation of the pattern:

And we see that even in the last rule shown here, only 18 of the 26 relevant cases in the rule are actually ever sampled during the generation of the pattern (from the particular, single-red-cell initial condition used). So this means that 8 cases in the rule are “undetermined” from the phenotype, implying that there are 3⁸ = 6561 possible genotypes (i.e. rules) that will give the same result.

So far we’ve mostly been talking about one particular random sequence of mutations. But what happens if we look at many possible such sequences? Here’s how the longest lifetime (or, in effect, “fitness”) increases for 100 different sequences of random mutations:

And what’s perhaps most notable here is that it seems as if these adaptive processes indeed don’t “get stuck”. It may take a while (with the result that there are long plateaus) but these pictures suggest that eventually “adaptive evolution will find a way”, and one will get to rules that show longer lifetimes—as the progressive development of the distribution of lifetimes reflects:

The Multiway Graph of All Possible Mutation Histories

In what we’ve done so far we’ve always been discussing particular paths of adaptive evolution, determined by particular sequences of random mutations. But a powerful way to get a more global view of the process of adaptive evolution is to look—in the spirit of our Physics Project, the ruliad, etc.—not just at individual paths of adaptive evolution, but instead at the multiway graph of all possible paths. (And in making a correspondence with biology, multiway graphs give us a way to talk about adaptive evolution not just of individual sequences of organisms, but also populations.)

To start our discussion, let’s consider not the 3-color cellular automata of the previous section, but instead (nearest-neighbor) 2-color cellular automata—for which there are just 128 possible relevant rules. How are these rules related by point mutations? We can construct a graph of every possible way that one rule from this set can be transformed to another by a single point mutation:

If we imagine 5-bit rather than 7-bit rules, there are only 16 relevant ones, and we can readily see that the graph of possible mutations has the form of a Boolean hypercube:

Let’s say we start from the “null rule” . Then we enumerate the rules obtained by a single point mutation (and therefore directly connected to the null rule in the graph above)—then we see what behavior they produce, say from the initial condition ……:

Some of these rules we can view as “making progress”, in the sense that they yield patterns with longer lifetimes (not impressively longer, just 2 rather than 1). But other rules “make no progress” or generate patterns that “live forever”. Keeping only mutations that don’t lead to shorter or infinite lifetimes, we can construct a multiway graph that shows all possible mutation paths:

Although this is a very small graph (with just 15 rules appearing), we can already see hints of some important phenomena. There are “fitness-neutral” mutations that can “go both ways”. But there are also plenty of mutations that only “go one way”—because the other way they would decrease fitness. And a notable feature of the graph is that once one’s “committed” to a particular part of the graph, one often can’t reach a different one—suggesting an analogy to the existence of distinct branches in the tree of life.

Moving beyond 2-color, nearest-neighbor (k = 2, r = 1) cellular automata, we can consider k = 2, r = ones. A typical such cellular automaton is:

For k = 2, r = 1 there were a total of 128 (= 2^{23 – 1}) relevant rules. For k = 2, r = , there are a total of 32,768 (= 2^{24 – 1}). Starting with the null rule, and again using initial condition ……, here are a few specific examples of adaptive evolution paths for such cellular automata:

And here is the beginning of the multiway graph for k = 2, r = rules—showing rules reached by up to two mutations starting from the null rule:

This graph contains many examples of “fitness-neutral sets”—rules that have the same fitness and that can be transformed into each other by mutations. A few examples of such fitness-neutral sets:

In the first case here, the “morphology of the phenotypic patterns” is the same for all “genotypic rules” in the fitness-neutral set. But in the other cases there are multiple morphologies within a single fitness-neutral set.

If we included all individual rules we’d get a complete k = 2, r = multiway graph with a total of 1884 nodes. But if we just include one representative from every fitness-neutral set, we get a more manageable multiway graph, with a total of 86 nodes:

Keeping only one representative from pairs of patterns that are related by left-right symmetry, we get a still-simpler graph, now with a total of 49 nodes:

There’s quite a lot of structure in this graph, with both divergence and convergence of possible paths. But overall, there’s a certain sense that different sections of the graph separate into distinct branches in which adaptive evolution in effect “pursues different ideas” about how to increase fitness (i.e. lifetime of patterns).

We can think of fitness-neutral sets as representing a certain kind of equivalence class of rules. There’s quite a range of possible structures to these sets—from ones with a single element to ones with many elements but few distinct morphologies, to ones with different morphologies for every element:

What about larger spaces of rules? For k = 2, r = 2 there are altogether about 2 billion (2^{25 – 1}) relevant rules. But if we choose to look only at left-right symmetric ones, this number is reduced to 524,288 (= 2¹⁹). Here are some examples of sequences of rules produced by adaptive evolution in this case, starting from the null rule, and allowing only mutations that preserve symmetry (and now using a single black cell as the initial condition):

Once again we can identify fitness-neutral sets—though this time, in the vast majority of cases, the patterns generated by all members of a given set are the same:

Reducing out fitness-neutral sets, we can then compute the complete (transitively reduced) multiway graph for symmetric k = 2, r = 2 rules (containing a total of 60 nodes):

By reducing out fitness-neutral sets, we’re creating a multiway graph in which every edge represents a mutation that “makes progress” in increasing fitness. But actual paths of adaptive evolution based on random sequences of mutations can do any amount of “rattling around” within fitness-neutral sets—not to mention “trying” mutations that decrease fitness—before reaching mutations that “make progress”. So this means that even though the reduced multiway graph we’ve drawn suggests that the maximum number of steps (i.e. mutations) needed to adaptively evolve from the null rule to any other is 9, it can actually take any number of steps because of the “rattling around” within fitness-neutral sets.

Here’s an example of a sequence of accepted mutations in a particular adaptive evolution process—with the mutations that “make progress” highlighted, and numbers indicating rejected mutations:

We can see “rattling around” in a fitness-neutral set, with a cycle of morphologies being generated. But while this represents one way to reach the final pattern, there are also plenty of others, potentially involving many fewer mutations. And indeed one can determine from the multiway graph that an absolutely shortest path is:

This involves the sequence of rules:

We’re starting from the null rule, and at each step making a single point mutation (though because of symmetry two bits can sometimes be changed). The first few mutations don’t end up changing the “phenotypic behavior”. But after a while, enough mutations (here 6) have built up that we get morphologically different behavior. And after just 3 more mutations, we end up with our final pattern.

Our original random sequence of mutations gets to the same result, but in a much more tortuous way, doing a total of 169 mutations which often cancel each other out:

In drawing a multiway graph, we’re defining what evolutionary paths are possible. But what about probabilities? If we assume that every point mutation is equally likely, we can in effect “analyze the flow” in the multiway graph, and determine the ultimate probability that each rule will be reached (with higher probabilities here shown redder):

The Fitness Landscape

Multiway graphs give a very global view of adaptive evolution. But in understanding the process of adaptive evolution, it’s also often useful to think somewhat more locally. We can imagine that all the possible rules are laid out in a certain space, and that adaptive evolution is trying to find appropriate paths in this space. Potentially we can suppose that there’s a “fitness landscape” defined in the space, and that adaptive evolution is trying to follow a path that progressively ascends to higher peaks of fitness.

Let’s consider again the very first example we gave above—of adaptive evolution in the space of 3-color cellular automata. At each step in this adaptive evolution, there are 52 possible point mutations that can be made to the rule. And one can think of each of these mutations as corresponding to making an “elementary move” in a different direction in the (26-dimensional) space of rules.

Here’s a visual representation of what’s going on, based on the particular path of adaptive evolution from our very first example above:

What we’re showing here is in effect the sequence of “decisions” that are being made to get us from one “fitness waypoint” to another. Different possible mutations are represented by different radial directions, with the length of each line being proportional to the fitness achieved by doing that mutation. At each step the gray disk represents the previous fitness. And what we see is that many possible mutations lead to lower fitness outcomes, shown “within the disk”. But there are at least some mutations that have higher fitness, and “escape the disk”.

In the multiway graph, we’d trace every mutation that leads to higher fitness. But for a particular path of adaptive evolution as we’ve discussed it so far, we imagine we always just pick at random one mutation from this set—as indicated here by a red line. (Later we’ll discuss different strategies.)

Our radial icons can be thought of as giving a representation of the “local derivative” at each point in the space of rules, with longer lines corresponding to directions with larger slopes “up the fitness landscape”.

But what happens if we want to “knit together” these local derivatives to form a picture of the whole space? Needless to say, it’s complicated. And as a first example, consider k = 2, r = 1 cellular automaton rules.

There are a total of 128 relevant such rules, that (as we discussed above) can be thought of as connected by point mutations to form a 7-dimensional Boolean hypercube. As also discussed above, of all 128 relevant rules, only 15 appear in adaptive evolution processes (the others are in effect never selected because they represent lower fitness). But now we can ask where these rules lie on the whole hypercube:

Each node here represents a rule, with the size of the highlighted nodes indicating their corresponding fitness (computed from lifetime with initial condition ……). The node shown in green corresponds to the null rule.

Rendering this in 3D, with fitness shown as height, we get what we can consider a “fitness landscape”:

And now we can think of our adaptive evolution as proceeding along paths that never go to nodes with lower height on this landscape.

We get a more filled-in “fitness landscape” when we look at k = 2, r = rules (here with initial condition ……):

Adaptive evolution must trace out a “never-go-down” path on this landscape:

Along this path, we can make “derivative” pictures like the ones above to represent “local topography” around each point—indicating which of the possible upwards-on-the-landscape directions is taken:

The rule space over which our “fitness landscape” is defined is ultimately discrete and effectively very high-dimensional (15-dimensional for k = 2, r = rules)—and it’s quite challenging to produce an interpretable visualization of it in 3D. We’d like it if we could lay out our rendering of the rule space so that rules which differ just by one mutation are a fixed (“elementary”) 2D distance apart. In general this won’t be possible, but we’re trying to at least approximate this by finding a good layout for the underlying “mutation graph”.

Using this layout we can in principle make a “fitness landscape surface” by interpolating between discrete points. It’s not clear how meaningful this is, but it’s perhaps useful in engaging our spatial intuition:

We can try machine learning and dimension reduction, operating on the set of “rule vectors” (i.e. outcome lists) that won’t be rejected in our adaptive evolution process—and the results are perhaps slightly better:

By the way, if we use this dimension reduction for rule space, here’s how the behavior of rules lays out:

And here, for comparison, is a feature space plot based on the visual appearance of these patterns:

The Whole Space: Exhaustive Search vs. Adaptive Evolution

In adaptive evolution, we start, say, from the null rule and then make random mutations to try to reach rules with progressively larger fitness. But what about just exhaustively searching the complete space of possible rules? The number of rules rapidly becomes unmanageably big—but some cases are definitely accessible:

For example, there are just 524,288 symmetric k = 2, r = 2 rules—of which 77,624 generate patterns with finite lifetimes. Ultimately, though, there are just 77 distinct phenotypic patterns that appear—with varying lifetimes and varying multiplicity (where at least in this case the multiplicity is always associated with “unused bits” in the rule):

How do these exhaustive results compare with what’s generated in the multiway graph of adaptive evolutions? They’re almost the same, but for the addition of the two extra cases

which are generated by rules of the form (where the gray entries don’t matter):

Why don’t such rules ever appear in our adaptive evolution? The reason is that there isn’t a chain of point mutations starting from the null rule that can reach these rules without going through rules that would be rejected by our adaptive evolution process. If we draw a multiway graph that includes every possible “acceptable” rule, then we’ll see a separate part in the graph, with its own root, that contains rules that can’t be reached by our adaptive evolution from the null rule:

So now if we look at all (symmetric k = 2, r = 2) rules, here’s the distribution of lifetimes we get:

The maximum, as seen above, is 65. The overall distribution roughly follows a power law, with an exponent around –3:

As we saw above, not all rules make use of all their bits (i.e. outcomes) in generating phenotypic patterns. But what we see is that the larger the lifetime achieved, the more bits tend to be needed:

And in a sense this isn’t surprising: as we’ll discuss later, we can expect to need “more bits in the program” to specify more elaborate behavior—or, in particular, behavior that embodies a larger number for lifetime.

So what about general (i.e. not necessarily symmetric) k = 2, r = 2 rules? There are 2³¹ ≅ 2 billion of these. If we exhaustively search through them, we find about 75 million that have finite lifetimes. The distribution of these lifetimes is:

Again it’s roughly a power law, but now with exponent around –3.5:

Here are the actual 100 patterns produced that have the longest lifetimes (in all asymmetric cases there are also rules giving left-right flipped patterns):

It’s interesting to see here a variety of “qualitatively different ideas” being used by different rules. Some (like the one with lifetime 151) we might somehow imagine could have been constructed specifically “for the purpose” of having their particular, long lifetime. But others (like the one with lifetime 308) somehow seem more “coincidental”—behaving in an apparently random way, and then just “happening to die out” after a certain number of steps.

Since we found these rules by exhaustive search, we know they’re the only possible ones with such long lifetimes (at least with k = 2, r = 2). So then we can infer that the ornate structures we see are in some sense necessary to achieve the objective of, say, having a finite lifetime of more than 100 steps. So that means that if we go through a process of adaptive evolution and achieve a lifetime above 100 steps, we see a complex pattern of behavior not because of “complicated choices in our process of adaptive evolution”, but rather because to achieve such a lifetime one has no choice but to use such a complex pattern. Or, in other words, the complexity we see is a reflection of “computational necessity”, not historical accidents of adaptive evolution.

Note also that (as we’ll discuss in more detail below) there are certain behaviors we can get, and others that we cannot. So, for example, there is a rule that gives lifetime 308, but none that gives lifetime 300. (Though, yes, if we used more complicated initial conditions or a more complicated family of rules we could find such a rule.)

Much as we saw in the symmetric k = 2, r = 2 case above, almost any long lifetimes require using all the available bits in the rule:

But, needless to say, there’s an exception—a pair of rules with lifetime 84 where the outcome for the case doesn’t matter:

But, OK, so can these long-lifetime rules be reached by single-mutation adaptive evolution from the null rule? Rather than trying to construct the whole multiway graph for the general k = 2, r = 2 case starting from the null rule, we can instead construct what’s in effect an inverse multiway graph in which we start from a given rule, then successively make all single point mutations that reach rules with progressively shorter lifetimes:

And what we see is that at least in this case such a procedure never reaches the null rule. The “furthest” it gets is to lifetime-2 rules, and among these rules the closest to the null rule are:

But it turns out that there’s no way to reach these 2-bit rules by a single point mutation from any of the 26 1-bit rules that aren’t rejected by our adaptive evolution process. And in fact this isn’t just an issue for this particular long-lifetime rule; it’s something quite general among k = 2 rules. And indeed, constructing the “forward” multiway graph starting from the null rule, we find we can only ever reach lifetime-1 rules.

Ultimately this is a particular feature of rules with just 2 colors—and it’s specific to starting with something like the null rule that has lifetime 1—but it’s an illustration of the fact that there can even be large swaths of rule space that can’t be reached by adaptive evolution with point mutations.

What about symmetric k = 2, r = 2 rules? Well, to maintain symmetry we have to deal with mutations that change not just one but two bits. And this turns out to mean that (except in the cases we discovered above) the inverse multiway system starting from long-lifetime rules always successfully reaches the null rule:

There’s something else to notice here, however. Looking at this graph, we see that there’s a way to get with just one 2-bit mutation from a lifetime-1 to a lifetime-65 rule:

We didn’t see this in our multiway graph above because we had applied transitive reduction to it. But if we don’t do that, we find that a few large lifetime jumps are possible—as we can see on this plot of possible lifetimes before and after a single point mutation:

Going beyond k = 2, r = 2 rules, we can consider symmetric k = 3, r = 1 rules, of which there are 3¹⁷, or about 129 million. The distribution of lifetimes in this case is

which again roughly fits a power law, again with exponent around –3.5:

But now the maximum lifetime found is not just 308, but 2194:

One again, there are some different “ideas” on display, with a few curious examples of convergence—such as the rules we see with lifetimes 989 and 990 (as well as 1068 and 1069) which give essentially the same patterns after just exchanging colors, and adding one “prefatory” step.

What about general k = 3, r = 1 rules? There are too many to easily search exhaustively. But directed random sampling reveals plenty of long-lifetime examples, such as:

And now the tail of very long lifetimes extends further, for example with:

It’s a little easier to see what the lifetime-10863 rule does if one visualizes it in sections (and adjusts colors to get more contrast):

Sampling 100 steps out every 2000 (as well as at the very end), we see elaborate alternation between periodic and seemingly random behavior—but none of it gives any obvious clue of the remarkable fact that after 10863 steps the whole pattern will die out:

The Issue of Undecidability

As our example criterion for the “fitness” of cellular automaton rules, we’ve used the lifetimes of the patterns they generate—always assuming that if the patterns don’t terminate at all they should be considered to have fitness zero.

But how can we tell if a pattern is going to terminate? In the previous section, for example, we saw patterns that live a very long time—but do eventually terminate.

Here are some examples of the first 100 steps of patterns generated by a few k = 3, r = 1 symmetric rules:

What will happen with these patterns? We know from what we see here that none of them have lifetimes less than 100 steps. But what would allow us to say more? In a few cases we can see that the patterns are periodic, or have obvious repeating structures, which means they’ll never terminate. But in the other cases there’s no obvious way to predict what will happen. Explicitly running the rules for another 100 steps we discover some more outcomes:

Going to 500 steps there are some surprises. Rule (a) becomes periodic after 388 steps; rules (o) and (v) terminate after 265 and 377 steps, respectively:

But is there a way to systematically say what will happen “in the end” with all the remaining rules? The answer is that in general there is not; it’s something that must be considered undecidable by any finite computation.

Given how comparatively simple the cellular automaton rules we’re considering are, we might have assumed that with all our sophisticated mathematical and computational methods we’d always be able to “jump ahead of them”—and figure out their outcome without the computational effort of explicitly running each step.

But the Principle of Computational Equivalence suggests that pretty much whenever the behavior of these rules isn’t obviously simple, it will in effect be of equal computational sophistication to any other system, and in particular to any methods that we might use to predict it. And the result is the phenomenon of computational irreducibility that implies that in many systems—presumably including most of the cellular automata here—there isn’t any way to figure out their outcome much more efficiently than by explicitly tracing each of their steps. So this means that to know what will happen “in the end”—after an infinite number of steps—might take an unlimited amount of computational effort. Or, in other words, it must be considered effectively undecidable by any finite computation.

As a practical matter we might look at the observed distribution of lifetimes for a particular type of cellular automaton, and become pretty confident that there won’t be longer finite lifetimes for that type of cellular automaton. But for the k = 3, r = 1 rules from the previous section, we might have been fairly confident that a few thousand steps was the longest lifetime that would ever occur—until we discovered the 10,863-step example.

So let’s say we run a particular rule for 10,000 steps and it hasn’t died out. How can we tell if it never will? Well, we have to construct a proof of some kind. And that’s easy to do if we can see that the pattern becomes, say, completely periodic. But in general, computational irreducibility implies we won’t be able to do it. Might there, though, still be special cases where we can? In effect, those would have to correspond to “pockets of computational reducibility” where we manage to find a compressed description of the cellular automaton behavior.

There are cases like this where there isn’t strict periodicity, but where in the end there’s basically repetitive behavior (here with period 480):

And there are cases of nested behavior, which is never periodic, but is nevertheless simple enough to be predictable:

But there are always surprises. Like this example—which eventually resolves to have period 6, but only after 7129 steps:

So what does all this mean for our adaptive evolution process? It implies that in principle we could miss a very long finite lifetime for a particular rule, assuming it to be infinite. In a biological analogy we might have a genome that seems to lead to unbounded perhaps-tumor-like growth—but where actually the growth in the end “unexpectedly” stops.

Computation Theoretic Perspectives and Busy Beavers

What we’re asking about the dying out of patterns in cellular automata is directly analogous to the classic halting problem for Turing machines, or the termination problem for term rewriting, Post tag systems, etc. And in looking for cellular automata that have the longest-lived patterns, we’re studying a cellular automaton analog of the so-called busy beaver problem for Turing machines.

We can summarize the results we’ve found so far (all for single-cell initial conditions):

The profiles (i.e. widths of nonzero cells) for the patterns generated by these rules are

and the “integrals” of these curves are what give the “areas” in the table above.

For the reasons described in the previous section, we can only be certain that we’ve found lower bounds on the actual maximum lifetime—though except in the last few cases listed it seems very likely that we do in fact have the maximum lifetime.

It’s somewhat sobering, though, to compare with known results for maximum (“busy beaver”) lifetimes for Turing machines (where now s is the number of Turing machine states, the Turing machines are started from blank tapes, and they are taken to “halt” when they reach a particular halt state):

Sufficiently small Turing machines can have only modest lifetimes. But even slightly bigger Turing machines can have vastly larger lifetimes. And in fact it’s a consequence of the undecidability of the halting problem for Turing machines that the maximum lifetime grows with the size of the Turing machine faster than any computable function (i.e. any function that can be computed in finite time by a Turing machine, or whose value can be proved by a finite proof in a finite axiom system).

But, OK, the maximum lifetime increases with the “size of the rule” for a Turing machine, or a cellular automaton. But what defines the “size of a rule”? Presumably it should be roughly the number of independent bits needed to specify the rule (which we can also think of as an approximate measure of its “information content”)—or something like log₂ of the number of possible rules of its type.

At the outset, we might imagine that all 2³² k = 2, r = 2 rules would need 32 bits to specify them. But as we discussed above, in some cases some of the bits in the rule don’t matter when it comes to determining the patterns they produce. And what we see is that the more bits that matter (and so have to be specified), the longer the lifetimes that are possible:

So far we’ve only been discussing cellular automata with single-cell initial conditions. But if we use more complicated initial conditions what we’re effectively doing is adding more information content into the system—with the result that maximum lifetimes can potentially get larger. And as an example, here are possible lifetimes for k = 2, r = rules with a sequence of possible initial conditions:

Probabilistic Approximations?

Cellular automata are at their core deterministic systems: given a particular cellular automaton rule and a particular initial condition, every aspect of the behavior that is generated is completely determined. But is there any way that we can approximate this behavior by some probabilistic model? Or might we at least usefully be able to use such a model if we look at the aggregate properties of large numbers of different rules?

One hint along these lines comes from the power-law distributions we found above for the frequencies of different possible lifetimes for cellular automata of given types. And we might wonder whether such distributions—and perhaps even their exponents—could be found from some probabilistic model.

One possible approach is to approximate a cellular automaton by a probabilistic process—say one in which a cell becomes black with probability p if it or either of its neighbors were black on the step before. Here are some examples of what can happen with this (“directed percolation”) setup:

The behavior varies greatly with p; for small p everything dies out, while for large p it fills in:

And indeed the final density—starting from random initial conditions—has a sharp (phase) transition at around p = 0.54 as one varies p:

If instead one starts from a single initial black cell one sees a slightly different transition:

One can also plot the probabilities for different “survival times” or “lifetimes” for the pattern:

And right around the transition the distribution of lifetimes follows a power law—that’s roughly τ^–1 (which happens to be what one gets from a mean field theory estimate).

So how does this relate to cellular automata? Let’s say we have a k = 2 rule, and we suppose that the colors of cells can be approximated as somehow random. Then we might suppose that the patterns we get could be like in our probabilistic model. And a potential source for the value of p to use would be the fraction of cases in the rule that give a black cell as output.

Plotting the lifetimes for k = 2, r = 2 rules against these fractions, we see that the longest lifetimes do occur when a little under half the outcomes are black (though notice this is also where the binomial distribution implies the largest number of rules are concentrated):

If we don’t try thinking about the details of cellular automaton evolution, but instead just consider the boundaries of finite-lifetime patterns we generate, we can imagine approximating these (say for symmetric rules) just by random walks—that when they collide correspond to the pattern dying out:

The standard theory of random walks then tells us that the probability to survive τ steps is proportional to τ^–3/2 for large τ—a power law, though not immediately one of the same ones that we’ve observed for our cellular automaton lifetimes.

Other Adaptive Evolution Strategies

In what we’ve done so far, we’ve always taken each step of our process of adaptive evolution to pick an outcome of equal or greater fitness. But what if we adopt a “more impatient” procedure in which at each step we insist on an outcome that has strictly greater fitness?

For k = 2 it’s simply not possible with this procedure (at least with a null initial condition) to “escape” the null rule; everything that can be reached with 1 mutation still has lifetime 1. With k = 3 it’s possible to go one step, but only one, as captured by this multiway graph:

But we’re assuming here that we have to reach greater fitness with just one mutation. What if we allow two mutations at a time? Well, then we can “make progress”. And here’s the multiway graph in this case for symmetric k = 2, r = 2 rules:

We don’t reach as many phenotypic patterns as by using single mutations and allowing “fitness-neutral moves”, but where we do get, we get much quicker, without any “back and forth” in fitness-neutral spaces.

If we allow up to 3 mutations, we get still further:

And indeed we seem to get a pretty good representative sampling of “what’s out there” in this rule space, even though we reach only 37 rules, compared to the 77,624 (albeit with many duplicated phenotypic patterns) from our standard approach allowing neutral moves.

For k = 3, r = 1 symmetric rules single mutations can get 2 steps:

But now if we allow up to 2 mutations, we can go much further—and the fact that we now don’t have to deal with neutral moves means we can explicitly construct at least the first few steps of the multiway graph in this case:

We can go further if at each step we just pick a random higher-fitness rule reached with two or fewer mutations:

The adaptive evolution histories we just showed can be generated in effect by randomly trying a series of possibilities at each step, then picking the first one that exhibits increased fitness. Another approach is to use what amounts to “local exhaustive search”: at each step, look at results from all possible mutations, and pick one that gives the largest fitness. At least in smaller rule spaces, it’s common that there will be several results with the same fitness, and as an example we’ll just pick among these at random:

One might think that this approach would in effect always be an optimization of the adaptive evolution process. But in practice its systematic character can end up making it get stuck, in some sense repeatedly “trying to do the same thing” even if it “isn’t working”.

Something of an opposite approach involves loosening our criteria for which paths can be chosen—and for example allowing paths that temporarily reduce fitness, say by one step of lifetime:

In effect here we’re allowing less-than-maximally-fit organisms to survive. And we can represent the overall structure of what’s happening by a multiway graph—which now includes “backtracking” to lower fitnesses:

But although the details are different, in the end it doesn’t seem as if allowing this kind of backtracking has any dramatic effect. Somehow the basic phenomena around the process of adaptive evolution are strong enough that most of the details of how the adaptive evolution is done don’t ultimately matter much.

An Aside: Sexual Reproduction

In everything we’ve done so far, we’ve been making mutations only to individual rules. But there’s another mechanism that exists in many biological organisms: sexual reproduction, in which in effect a pair of rules (i.e. genomes) get mixed to produce a new rule. As a simple model of the crossover that typically happens with actual genomes, we can take two rules, and splice together the beginning of one with the end of the other:

In general there will be many ways to combine pairs of rules like this. In a direct analogy to our Physics Project, we can represent such “recombinations” as “events” that take two rules and produce one:

The analog of our multiway graph for all possible paths of adaptive evolution by mutations is now what we call in our Physics Project a token-event graph:

In dealing just with mutations we were able to take a single rule and progressively modify it. Now we always have to work with a “population” of rules, combining them two at a time to generate new rules. We can represent conceivable combinations among one set of rules as follows:

There are at this point many different choices we could make about how to set up our model. The particular approach we’ll use selects just n of the = n (n – 1)/2 possible combinations:

Then for each of these selected combinations we attempt a crossover, keeping those “children” (drawn here between their parents) that are not rejected as a result of having lower fitness:

Finally, to “maintain our gene pool”, we carry forward parents selected at random, so that we still end up with n rules. (And, yes, even though we’ve attempted to make this whole procedure as clean as possible, it’s still a mess—which seems to be inevitable, and which has, as we’ll discuss below, bedeviled computational studies of evolution in the past.)

OK, so what happens when we apply this procedure, say to k = 3, r = 1 rules? We’ll pick 4 rules at random as our initial population (and, yes, two happen to produce the same pattern):

Then in a sequence of steps we’ll successively pick various combinations:

And here are the distinct “phenotype patterns” produced in this process (note that even though there can be multiple copies of the same phenotype pattern, the underlying genotype rules are always distinct):

As a final form of summarization we can just plot the successive fitnesses of the patterns we generate (with the size of each dot reflecting the number of times a particular fitness occurs):

In this case we reach a steady state after 9 steps. The larger the population the longer the adaptive evolution will typically keep going. Here are a couple of examples with population 10, showing all the patterns obtained:

Showing in each case only the longest-lifetime rule found so far we get:

The results aren’t obviously different from what we were finding with mutation alone—even though now we’ve got a much more complicated model, with a whole population of rules rather than a single rule. (One obvious difference, though, is that here we can end up with overall cycles of populations of rules, whereas in the pure-mutation case that can only happen among fitness-neutral rules.)

Here are some additional examples—now obtained after 500 steps with population 25

and with population 50:

And so far as one can tell, even here there are no substantial differences from what we saw with mutation. Certainly there are detailed features introduced by sexual reproduction and crossover, but for our purposes in understanding the big picture of what’s happening in adaptive evolution it seems sufficient to do as we have done so far, and consider only mutation.

An Even More Minimal Model

By investigating adaptive evolution in cellular automata we’re already making dramatic simplifications relative, say, to actual biology. But in the effort to understand the essence of phenomena we see, it’s helpful to go even further—and instead of thinking about computational rules and their behavior, just think about vertices on a “mutation graph”, each assigned a certain fitness.

As an example, we can set up a 2D grid, assigning each point a certain random fitness:

And then, starting from a minimum-fitness point, we can follow the same kind of adaptive evolution procedure as above, at each step going to a neighboring point with an equal or greater fitness:

Typically we don’t manage to go far before we get stuck, though with the uniform distribution of fitness values used here, we still usually end on a fairly large fitness value.

We can summarize the possible paths we can take by the multiway graph:

In our cellular automaton rule space—and, for that matter, in biology—neighboring points don’t just have independent random fitnesses; instead, the fitnesses are determined by a definite computational procedure. So as a simple approximation, we can just take the fitness of each point to be a particular function of its graph coordinates. If the function forms something like a “uniform hill”, then the adaptive evolution procedure will just climb it:

But as soon as the function has “systematic bumpiness” there’s a tremendous tendency to quickly get stuck:

And if there’s some “unexpected spot of high fitness”, adaptive evolution typically won’t find it (and it certainly won’t if it’s surrounded by a lower-fitness “moat”):

So what happens if we increase the dimensionality of the “mutation space” in which we’re operating? Basically it becomes easier to find a path that increases fitness:

And we can see this, for example, if we look at Boolean hypercubes in increasing numbers of dimensions:

But ultimately this relies on the fact that in the neighborhood reachable by mutations from a given point, there’ll be a “sufficiently random” collection of fitness values that it’ll (likely) be possible to find a “direction” that’s “going up” in fitness. Yet this alone won’t in general be enough, because we also need it to be the case that there’s enough regularity in the fitness landscape that we can systematically navigate it to find its maximum—and that the maximum is not somehow “unexpected and isolated”.

What Can Adaptive Evolution Achieve?

We’ve seen that adaptive evolution can be surprisingly successful at finding cellular automata that produce patterns with long but finite lifetimes. But what about other types of “traits”? What can (and cannot) adaptive evolution ultimately manage to do?

For example, what if we’re trying to find cellular automata whose patterns don’t just live “as long as possible” but instead die after a specific number of steps? It’s clear that within any finite set of rules (say with particular k and r) there’ll only be a limited collection of possible lifetimes. For symmetric k = 2, r = 2 rules, for example, the possible lifetimes are:

But as soon as we’re dealing even with k = 3, r = 1 symmetric rules it’s already in principle possible to get every lifetime up to 100. But what about adaptive evolution? How well does it do at reaching rules with all those lifetimes? Let’s say we do single point mutation as before, but now we “accept” a mutation if it leads not specifically to a larger finite lifetime, but to a lifetime that is closer in absolute magnitude to some desired lifetime. (Strictly, and importantly, in both cases we also allow “fitness-neutral” mutations that leave the lifetime the same.)

Here are examples of what happens if we try to adaptively evolve to get lifetime exactly 50 in k = 3, r = 1 rules:

It gets close—and sometimes it overshoots—but, at least in these particular examples, it never quite makes it. Here’s what we see if we look at the lifetimes achieved with 100 different random sequences of mutations:

Basically they mostly get stuck at lifetimes close to 50, but not exactly 50. It’s not that k = 3, r = 1 rules can’t yield lifetime 50; exhaustive search shows that even many symmetric such rules can:

It’s just that our adaptive evolution process usually gets stuck before it reaches rules like these. Even though there’s usually enough “room to maneuver” in k = 3, r = 1 rule space to get to generally longer lifetimes, there’s not enough to specifically get to lifetime 50.

But what about k = 4, r = 1 rule space? There are now not 10¹² but about 10³⁸ possible rules. And in this rule space it becomes quite routine to be able to reach lifetime 50 through adaptive evolution:

It can sometimes take a while, but most of the time in this rule space it’s possible to get exactly to lifetime 50:

What happens with other “lifetime goals”? Even symmetric k = 3, r = 1 rules can achieve many lifetime values:

Indeed, the first “missing” values are 129, 132, 139, etc. And, for example, many multiples of 50 can be achieved:

But it becomes increasingly difficult for adaptive evolution to reach these specific goals. Increasing the size of the rule space always seems to help; so for example with k = 4, r = 1, if one’s aiming for lifetime 100, the actual distribution of lifetimes reached is:

In general the distribution gets broader as the lifetime sought gets larger:

We saw above that across the whole space of, say, k = 4, r = 1 rules, the frequency of progressively larger lifetimes falls roughly according to a power law. So this means that the fractional region in rule space that achieves a given lifetime gets progressively smaller—with the result that typically the paths followed by adaptive evolution are progressively more likely to get stuck before they reach it.

OK, so what about other kinds of objectives? Say ones more related to the morphologies of patterns? As a simple example, let’s consider the objective of maximizing the “widths” of finite-lifetime patterns. We can try to achieve this by adaptive evolution in which we reject any mutations that lead to decreased width (where “width” is defined as the maximum horizontal extent of the pattern). And once again this process manages to “discover” all sorts of “mechanisms” for achieving larger widths (here each pattern is labeled by its height—i.e. lifetime—and width):

There are certain structural constraints here. For example, the width can’t be too large relative to the height—because if it’s too large, patterns tend to grow forever.

But what if we specifically try to select for maximal “pattern aspect ratio” (i.e. ratio of width to height)? In essentially every case so far, adaptive evolution has in effect “invented many different mechanisms” to achieve whatever objective we’ve defined. But here it turns out we essentially see “the same idea” being used over and over again—presumably because this is the only way to achieve our objective given the overall structure of how the underlying rules we’re using work:

What if we ask something more specific? Like, say, that the aspect ratio be as close to 3 as possible. Much of the time the “solution” that adaptive evolution finds is the correct if trivial:

But sometimes it finds another solution—and often a surprisingly elaborate and complicated one:

How about if our goal is an aspect ratio of π ≈ 3.14? It turns out adaptive evolution can still do rather well here even just with the symmetric k = 3, r = 1 rules that we’re using:

We can also ask about properties of the “inside” of the pattern. For example, we can ask to maximize the lengths of uniform runs of nonwhite cells in the center column of the pattern. And, once again, adaptive evolution can successfully lead us to rules (like these random examples) where this is large:

We can go on and get still more detailed, say asking about runs of particular lengths, or the presence or number of particular subpatterns. And eventually—just like when we asked for too long a lifetime—we’ll find that the cases we’re looking for are “too sparse”, and adaptive evolution (at least in a given rule space) won’t be able to find them, even if exhaustive search could still identify at least a few examples.

But just what kinds of objectives (or fitness functions) can be handled how well by adaptive evolution, operating for example on the “raw material” of cellular automata? It’s an important question—an analog of which is also central to the investigation of machine learning. But as of now we don’t really have the tools to address it. It’s somehow reminiscent of asking what kinds of functions can be approximated how well by different methods or basis functions. But it’s more complicated. Solving it, though, would tell us a lot about the “reach” of adaptive evolution processes, not only for biology but also for machine learning.

What It Means for What’s Going On in Biology

How do biological organisms manage to be the way they are, with all their complex and seemingly clever solutions to such a wide range of challenges? Is it just natural selection that does it, or is there in effect more going on? And if “natural selection does it”, how does it actually manage it?

From the point of view of traditional engineering what we see in biology is often very surprising, and much more complex and “clever” than we’d imagine ever being able to create ourselves. But is the secret of biology in a sense just natural selection? Well, actually, there’s often an analog of natural selection going on even in engineering, as different designs get tried and only some get selected. But at least in traditional engineering a key feature is that one always tries to come up with designs where one can foresee their consequences.

But biology is different. Mutations to genomes just happen, without any notion that their consequences can be foreseen. But still one might assume that—when guided by natural selection—the results wouldn’t be too different to what we’d get in traditional engineering.

But there’s a crucial piece of intuition missing here. And it has to do with how randomly chosen programs behave. We might have assumed (based on our typical experience with programs we explicitly construct for particular purposes) that at least a simple random program wouldn’t ever do anything terribly interesting or complicated.

But the surprising discovery I made in the early 1980s is that this isn’t true. And instead, it’s a ubiquitous phenomenon that in the computational universe of possible programs, one can get immense complexity even from very simple programs. So this means that as mutation operates on a genome, it’s essentially inevitable that it’ll end up sampling programs that show highly complex behavior. At the outset, one might have imagined that such complexity could only be achieved by careful design and would inevitably be at best rare. But the surprising fact is that—because of how things fundamentally work in the computational universe—it’s instead easy to get.

But what does complexity have to do with creating “successful organisms”? To create a “successful organism” that can prosper in a particular environment there fundamentally has to be some way to get to a genome that will “solve the necessary problems”. And this is where natural selection comes in. But the fact that it can work is something that’s not at all obvious.

There are really two issues. The first is whether a program (i.e. genome) even exists that will “solve the necessary problems”. And the second is whether such a program can be found by a “thread” of adaptive evolution that goes only through intermediate states that are “fit enough” to survive. As it turns out, both these issues are related to the same fundamental features of computation—which are also responsible for the ubiquitous appearance of complexity.

Given some underlying framework—like cellular automata, or like the basic apparatus of life—is there some rule that can be implemented in that framework that will achieve some particular (computational) objective? The Principle of Computational Equivalence says that generically the answer will be yes. In effect, given almost any “underlying hardware”, it’ll ultimately be possible to come up with “software” (i.e. a rule) that achieves almost any (“physically possible”) given objective—like growing an organism of at least some kind that can survive in a particular environment. But how can we actually find a rule that achieves this?

In principle we could do exhaustive search. But that will be exponentially difficult—and in all but toy cases will be utterly infeasible in practice. So what about adaptive evolution? Well, that’s the big question. And what we’ve seen here is that—rather surprisingly—simple mutation and selection (i.e. the mechanisms of natural selection) very often provide a dramatic shortcut for finding rules that do what we want.

So why is this? In effect, adaptive evolution is finding a path through rule space that gets to where we want to go. But the surprising part is that it’s managing to do this one step at a time. It’s just trying random variations (i.e. mutations) and as soon as it finds one that’s not a “step down in fitness”, it’ll “take it”, and keep going. At the outset it’s certainly not obvious that this will work. In particular, it could be that at some point there just won’t be any “way forward”. All “directions” will lead only to lower fitness, and in effect the adaptive evolution will get stuck.

But the key observation from the experiments in our simple model here is that this typically doesn’t happen. And there seem to be basically two things going on. The first is that rule space is in effect very high-dimensional. So that means there are “many directions to choose from” in trying to find one that will allow one to “take a step forward”. But on its own this isn’t enough. Because there could be correlations between these directions that would mean that if one’s blocked in one direction one would inevitably be blocked in all others.

So why doesn’t this happen? Well, it seems to be the result of the fundamental computational phenomenon of computational irreducibility. A traditional view based on experience with mathematical science had been that if one knew the underlying rule for a system then this would immediately let one predict what the system would do. But what became clear from my explorations in the 1980s and 1990s is that in the computational universe this generically isn’t true. And instead, that the only way one can systematically find out what most computational systems will do is explicitly to run their rules, step by step, doing in effect the same irreducible amount of computational work that they do.

So if one’s just presented with behavior from the system one won’t be in a position to “decode it” and “see its simple origins”. Unless one’s capable of doing as much computational work as the system itself, one will just have to consider what it’s doing as (more or less) “random”. And indeed this seems to be at the root of many important phenomena, such as the Second Law of thermodynamics. And I also suspect it’s at the root of the effectiveness of adaptive evolution, notably in biology.

Because what computational irreducibility implies is that around every point in rule space there’ll be a certain “effective randomness” to fitnesses one sees. And if there are many dimensions to rule space that means it’s overwhelmingly likely that there’ll be “paths to success” in some directions from that point.

But will the adaptive evolution find them? We’ve assumed that there are a series of mutations to the rule, all happening “at random”. And the point is that if there are n elements in the rule, then after some fraction of n mutations we should find our “success direction”. (If we were doing exhaustive search, we’d instead have to try about kⁿ possible rules.)

At the outset it might seem conceivable that the sequence of mutations could somehow “cleverly probe” the structure of rule space, “knowing” what directions would or would not be successful. But the whole point is that going from a rule (i.e. genotype) to its behavior (i.e. phenotype) is generically a computationally irreducible process. So assuming that mutations are generated in a computationally bounded way it’s inevitable that they can’t “break computational irreducibility” and so will “experience” the fitness landscape in rule space as “effectively random”.

OK, but what about “achieving the characteristics an organism needs”? What seems to be critical is that these characteristics are in a sense computationally simple. We want an organism to live long enough, or be tall enough, or whatever. It’s not that we need the organism to perform some specific computationally irreducible task. Yes, there are all sorts of computationally irreducible processes happening in the actual development and behavior of an organism. But as far as biological evolution is concerned all that matters is ultimately some computationally simple measure of fitness. It’s as if biological evolution is—in the sense of my recent observer theory—a computationally bounded observer of underlying computationally irreducible processes.

And to the observer what emerges is the “simple law” of biological evolution, and the idea that, yes, it is possible just by natural selection to successfully generate all sorts of characteristics.

There are all sorts of consequences of this for thinking about biology. For example, in thinking about where complexity in biology “comes from”. Is it “generated by natural selection”, perhaps reflecting the complicated sequence of historical accidents embodied in the particular collection of mutations that occurred? Or is it from somewhere else?

In the picture we’ve developed here it’s basically from somewhere else—because it’s essentially a reflection of computational irreducibility. Having said that, we should remember that the very possibility of being able to have organisms with such a wide range of different forms and functions is a consequence of the universal computational character of their underlying setup, which in turn is closely tied to computational irreducibility.

And it’s in effect because natural selection is so coarse in its operation that it does not somehow avoid the ubiquitous computational irreducibility that exists in rule space, with the result that when we “look inside” biological systems we tend to see computational irreducibility and the complexity associated with it.

Something that we’ve seen over and over again here is that, yes, adaptive evolution manages to “solve a problem”. But its solution looks very complex to us. There might be some “simple engineering solution”—involving, say, a very regular pattern of behavior. But that’s not what adaptive evolution finds; instead it finds something that to us is typically very surprising—very often an “unexpectedly clever” solution in which lots of pieces fit together just right, in a way that our usual “understand-what’s-going-on” engineering practices would never let us invent.

We might not have expected anything like this to emerge from the simple process of adaptive evolution. But—as the models we’ve studied here highlight—it seems to be an inevitable formal consequence of core features of computational systems. And as soon as we recognize that biological systems can be viewed as computational, then it also becomes something inevitable for them—and something we can view as in a sense formally derivable for them.

At the outset we might not have been able to say “what matters” in the emergence of complexity in biology. But from the models we’ve studied, and the arguments we’ve made, we seem to have quite firmly established that it’s a fundamentally computational phenomenon, that relies only on certain general computational features of biological systems, and doesn’t depend on their particular detailed components and structure.

But in the end, how “generic” is the complexity that comes out of adaptive evolution? In other words, if we were to pick programs, say completely at random, how different would the complexity they produce be from the complexity we see in programs that have been adaptively evolved “for a purpose”? The answer isn’t clear—though to know it would provide important foundational input for theoretical biology.

One has the general impression that computational irreducibility is a strong enough phenomenon that it’s the “dominant force” that determines behavior and produces complexity. But there’s still usually something a bit different about the patterns we see from rules we’ve found by adaptive evolution, compared to rules we pick at random. Often there seems to be a certain additional level of “apparent mechanism”. The details still look complicated and in some ways quite random, but there seems to be a kind of “overall orchestration” to what’s going on.

And whenever we can identify such regularities it’s a sign of some kind of computational reducibility. There’s still plenty of computational irreducibility at work. But “high fitness” rules that we find through adaptive evolution typically seem to exhibit traces of their specialness—that manifests in at least a certain amount of computational reducibility.

Whenever we manage to come up with a “narrative explanation” or a “natural law” for something, it’s a sign that we’ve found a pocket of computational reducibility. If we say that a cellular automaton manages to live long because it generates certain robust geometric patterns—or, for that matter, that an organism lives long because it proofreads its DNA—we’re giving a narrative that’s based on computational reducibility.

And indeed whenever we can successfully identify a “mechanism” in our cellular automaton behavior, we’re in effect seeing computational reducibility. But what can we say about the aggregate of a whole collection of mechanisms?

In a different context I’ve discussed the concept of a “mechanoidal phase”, distinguished, say, from solids and liquids by the presence of a “bulk orchestration” of underlying components. It’s something closely related to class 4 behavior. And it’s interesting to note that if we look, for example, at the rules we found from adaptive evolution at the end of the previous section, their evolution from random initial conditions mostly shows characteristic class 4 behavior:

In other words, adaptive evolution is potentially bringing us to “characteristically special” places in rule space—perhaps suggesting that there’s something “characteristically special” about the kind of structures that are produced in biological systems. And if we could find a way to make general statements about that “characteristic specialness” it would potentially lead us to a framework for constructing a new broad formal theory in biology.

Correspondence with Biological Phenomena

The models we’ve studied here are extremely simple in their basic construction. And at some level it’s remarkable that—without for example including any biophysics or biochemistry—they can get anywhere at all in capturing features of biological systems and biological evolution.

In a sense this is ultimately a reflection of the fundamentally computational character of biology—and the generality of computational phenomena. But it’s very striking that even the patterns of cellular automaton behavior we see look very “lifelike and organic”.

In actual biology even the shortest genomes are vastly longer than the tiny cellular automaton rules we’ve considered. But even by the time we’re looking at the length-27 “genomic sequences” in k = 3, r = 1 cellular automata, there are already 3 trillion possible sequences, which seems to be enough to see many core “combinatorially driven” biology-like phenomena.

The running of a cellular automaton rule might also at first seem far away from the actual processes that create biological organisms—involving as they do things like the construction of proteins and the formation of elaborate functional and spatial structures. But there are more analogies than one might at first imagine. For example, it’s common for only particular cases in the cellular automaton rule to be used in a given region of the pattern that’s formed, much as particular genes are typically turned on in different tissues in biological organisms.

And, for example, the “geometrical restriction” to a simple 1D array of “cells” doesn’t seem to matter much as soon as there’s sophisticated computation going on; we still get lots of structures that are actually surprisingly reminiscent of typical patterns of biological growth.

One of the defining features of biological organisms is their capability for self-reproduction. And indeed if it wasn’t for this kind of “copying” there wouldn’t be anything like adaptive evolution to discuss. Our models don’t attempt to derive self-reproduction; they just introduce it as something built into the models.

And although we’ve considered several variants, we’re basically also just building into our models the idea of mutations. And what we find is that it seems as if single point mutations made one at a time are enough to capture basic features of adaptive evolution.

We’ve also primarily considered what amounts to a single lineage—in which there’s just a single rule (or genome) at a given step. We do mutations, and we mostly “implement natural selection” just by keeping only rules that lead to patterns whose fitness is no less than what we had before.

If we had a whole population of rules it probably wouldn’t be so significant, but in the simple setup we’re using, it turns out to be important that we don’t reject “fitness-neutral mutations”. And indeed we’ve seen many examples where the system wanders around fitness-neutral regions of rule space before finally “discovering” some “innovation” that allows it to increase fitness. The way our models are set up, that “wandering” always involves changes in the “genotype”—but usually at most minor changes in the phenotype. So it’s very typical to see long periods of “apparent equilibrium” in which the phenotype changes rather little, followed by a “jump” to a new fitness level and a rather different phenotype.

And this observation seems quite aligned with the phenomenon of “punctuated equilibrium” often reported in the fossil record of actual biological evolution.

Another key feature of biological organisms and biological evolution is the formation of distinct species, as well as distinct phyla, etc. And indeed we ubiquitously see something that seems to be directly analogous in our multiway graphs of all possible paths of adaptive evolution. Typically we see distinct branches forming, based on what seem like “different mechanisms” for achieving fitness.

No doubt in actual biology there are all sorts of detailed phenomena related to reproductive or spatial isolation. But in our models the core phenomenon that seems to lead to the analog of “branching in the tree of life” is the existence of “distinctly different computational mechanisms” in different parts of rule space. It’s worth noting that at least with our finite rule spaces, branches can die out, with no “successor species” appearing the multiway graph.

And indeed looking at the actual patterns produced by rules in different parts of the multiway graph it’s easy to imagine morphologically based taxonomic classifications—that would be somewhat, though not perfectly, aligned with the phylogenetic tree defined by actual rule mutations. (At a morphological level we quite often see some level of “convergent evolution” in our multiway graphs; in small examples we sometimes also see actual “genomic convergence”—which will typically be astronomically rare in actual biological systems.)

One of the remarkable features of our models is that they allow quite global investigation of the “overall history” of adaptive evolution. In many of the simple cases we’ve discussed, the rule space we’re using is small enough that in a comparatively modest number of mutation steps we get to the “highest fitness we can reach”. But (as the examples we saw in Turing machines suggest) expanding the size of the rules we’re using even just a little can be expected to be sufficient to allow us to get astronomically further.

And the further we go, the more “mechanisms” will be “invented”. It’s an inevitable feature of systems that involve computational irreducibility that there are new and unpredictable things that will go on showing up forever—along with new pockets of computational reducibility. So even after a few billion years—and the trillion generations and 10⁴⁰ or so organisms that have ever lived—there’s still infinitely further for biological evolution to go, and more and more branches to be initiated in the tree of life, involving more and more “new mechanisms”.

I suppose one might imagine that at some point biological organisms would reach a “maximum fitness”, and go no further. But even in our simple model with fitness measured in terms of pattern lifetime, there’ll be no upper limit on fitness; given any particular lifetime, it’s a feature of the fundamental theory of computation that there’ll always be a program that will yield a larger lifetime. Still, one might think, at some point enough is enough: the giraffe’s neck is long enough, etc. But if nothing else, competition between organisms will always drive things forward: yes, a particular lineage of organisms achieved a certain fitness, but then another lineage can come along and get to that fitness too, forcing the first lineage to go even further so as to not lose out.

Of course, in our simple model we’re not explicitly accounting for interactions with other organisms—or for detailed properties of the environment, as well as countless other effects. And no doubt there are many biological phenomena that depend on these effects. But the key point here is that even without explicitly accounting for any of these effects, our simple model still seems to capture many core features of biological evolution. Biological evolution—and, indeed, adaptive evolution in general—is, it seems, fundamentally a computational phenomenon that robustly emerges quite independent of the details of systems.

In the past few years our Physics Project has given strong evidence that the foundations of physics are fundamentally computational—with the core laws of physics arising as inevitable consequences of the way observers like us “parse” the ruliad of all possible computational processes. And what we’ve seen here now suggests that there’s a remarkable commonality between the foundations of physics and biology. Both are anchored in computational irreducibility. And both sample slices of computational reducibility. Physics because that’s what observers like us do to get descriptions of the world that fit in our finite minds. Biology because that’s what biological evolution does in order to achieve the “coarse objectives” set by natural selection.

The intuition of physics tends to be that there are ultimately simple models for things, whereas in biology there’s a certain sense that everything is always almost infinitely complicated, with a new effect to consider at every turn. But presumably that’s in large part because what we study in biology tends to quickly come face to face with computational irreducibility—whereas in physics we’ve been able to find things to study that avoid this. But now the commonality in foundations between physics and biology suggests that there should also be in biology the kind of structure we have in physics—complete with general laws that allow us to make useful, broad statements. And perhaps the simple model I’ve presented here can help lead us there—and in the end help build up a new paradigm for thinking about biology in a fundamentally theoretical way.

Historical Notes

There’s a long—if circuitous—history to the things I’m discussing here. Basic notions of heredity—particularly for humans—were already widely recognized in antiquity. Plant breeding was practiced from the earliest days of agriculture, but it wasn’t until the late 1700s that any kind of systematic selective breeding of animals began to be commonplace. Then in 1859 Charles Darwin described the idea of “natural selection” whereby competition of organisms in their natural environment could act like artificial selection, and, he posited, would over long periods lead to the development of new species. He ended his Origin of Species with the claim that:

… from the war of nature … the production of the higher animals, directly follows. … and whilst this planet has gone cycling on according to the fixed law of gravity, from so simple a beginning endless forms most beautiful and most wonderful have been, and are being, evolved.

What he appears to have thought is that there would somehow follow from natural selection a general law—like the law of gravity—that would lead to the evolution of progressively more complex organisms, culminating in the “higher animals”. But absent the kind of model I’m discussing here, nothing in the later development of traditional evolutionary theory really successfully supported this—or was able to give much analysis of it.

Right around the same time as Darwin’s Origin of Species, Gregor Mendel began to identify simple probabilistic laws of inheritance—and when his work was rediscovered at the beginning of the 1900s it was used to develop mathematical models of the frequencies of genetic traits in populations of organisms, with key contributions to what became the field of population genetics being made in the 1920s and 1930s by J. B. S. Haldane, R. A. Fisher and Sewall Wright, who came up with the concept of a “fitness landscape”.

On a quite separate track there had been efforts ever since antiquity to classify and understand the growth and form of biological organisms, sometimes by analogy to physical or mathematical ideas—and by the 1930s it seemed fairly clear that chemical messengers were somehow involved in the control of growth processes. But the mathematical methods used for example in population genetics basically only handled discrete traits (or simple numerical ones accessible to biometry), and didn’t really have anything to say about something like the development of complexity in the forms of biological organisms.

The 1940s saw the introduction of what amounted to electrical-engineering-inspired approaches to biology, often under the banner of cybernetics. Idealized neural networks were introduced by Warren McCulloch and Walter Pitts in 1943, and soon the idea emerged (notably in the work of Donald Hebb in 1949) that learning in such systems could occur through a kind of adaptive evolution process. And by the time practical electronic computing began to emerge in the 1950s there was widespread belief that ideas from biology—including evolution—would be useful as an inspiration for what could be done. Often what would now just be described as adaptive algorithms were couched in biological evolution terms. And even when iterative methods were used for optimization (say in industrial production or engineering design) they were sometimes presented as being grounded in biological evolution.

Meanwhile, by the 1960s, there began to be what amounted to Monte Carlo simulations of population-genetics-style evolutionary processes. A particularly elaborate example was work by Nils Barricelli on what he called “numeric evolution” in which a fairly complicated numerical-cellular-automaton-like “competition between organisms” program with “randomness” injected from details of data layout in computer memory showed what he claimed to be biological-evolution-like phenomena (such as symbiosis and parasitism).

In a different direction there was an attempt—notably by John von Neumann—to “mathematicize the foundations of biology” leading by the late 1950s to what we’d now call 2D cellular automata “engineered” in complicated ways to show phenomena like self-reproduction. The followup to this was mostly early-theoretical-computer-science work, with no particular connection to biology, and no serious mention of adaptive evolution. When the Game of Life was introduced in 1970 it was widely noted as “doing lifelike things”, but essentially no scientific work was done in this direction. By the 1970s, though, L-systems and fractals had introduced the idea of recursive tree-like or nested structures that could be generated by simple algorithms and rendered by computer graphics—and seemed to give forms close to some seen in biology. My own work on 1D cellular automata (starting in 1981) focused on systematic scientific investigation of simple programs and what they do—with the surprising conclusion that even very simple programs can produce highly complex behavior. But while I saw this as informing the generation of complexity in things like the growth of biological organisms, I didn’t at the time (as I’ll describe below) end up seriously exploring any adaptive evolution angles.

Still another thread of development concerned applying biological-like evolution not just to parameters but to operations in programs. And for example in 1958 Richard Friedberg at IBM tried making random changes to instructions in machine-code programs, but didn’t manage to get this to do much. (Twenty years later, superoptimizers in practical compilers did begin to successfully use such techniques.) Then in the 1960s, John Holland (who had at first studied learning in neural nets, and was then influenced by Arthur Burks who had worked on cellular automata with von Neumann) suggested representing what amounted to programs by simple strings of symbols that could readily be modified like genomic sequences. The typical idea was to interpret the symbols as computational operations—and to assign a “fitness” based on the outcome of those operations. A “genetic algorithm” could then be set up by having a population of strings that was adaptively evolved. Through the 1970s and 1980s occasional practical successes were reported with this approach, particularly in optimization and data classification—with much being made of the importance of sexual-reproduction-inspired crossover operations. (Something that began to be used in the 1980s was the much simpler approach of simulated annealing—that involves randomly changing values rather than programs.)

By the beginning of the 1980s the idea had also emerged of adaptively modifying the structure of mathematical expressions—and of symbolic expressions representing programs. There were notable applications in computer graphics (e.g. by Karl Sims) as well as to things like the 1984 Core War “game” involving competition between programs in a virtual machine. In the 1990s John Koza was instrumental in developing the idea of “genetic programming”, notably as a way to “automatically create inventions”, for example in areas like circuit and antenna design. And indeed to this day scattered applications of these methods continue to pop up, particularly in geometrical and mechanical design.

From the very beginning there’d been controversy around Darwin’s ideas about evolution. First, there was the issue of conflict with religious accounts of creation. But there were also—often vigorous—disagreements within the scientific community about the interpretation of the fossil record and about how large-scale evolution was really supposed to operate. A notable issue—still very active in the 1980s—was the relationship between the “freedom of evolution” and the constraints imposed by the actual dynamics of growth in organisms (and interactions between organisms). And despite much insistence that the only reasonable “scientific” (as opposed to religious) point of view was that “natural selection is all there is”, there were nagging mysteries that suggested there must be other forces at work.

Building on the possibilities of computer experimentation (as well as things like my work on cellular automata) there emerged in the mid-1980s, particularly through the efforts of Chris Langton, a focus on investigating computational models of “artificial life”. This resulted in all sorts of simulations of ecosystems, etc. that did produce a variety of evolution-related phenomena known from field biology—but typically the models were far too complex in their structure for it to be possible to extract fundamental conclusions from them. Still, there continued to be specific, simpler experiments. For example, in 1986, for his book The Blind Watchmaker, Richard Dawkins made pictures of what he called “biomorphs”, produced by adaptively adjusting parameters for a simple tree-growth algorithm based on the overall shapes generated.

In the 1980s, stimulated by my work, there were various isolated studies of “rule evolution” in cellular automata (as well as art and museum exhibits based on this), and in the 1990s there was more systematic work—notably by Jim Crutchfield and Melanie Mitchell—on using genetic algorithms to try to evolve cellular automaton rules to solve tasks like density classification. (Around this time “evolutionary computation” also began to emerge as a general term covering genetic algorithms and other usually-biology-inspired adaptive computational methods.)

Meanwhile, accelerating in the 1990s, there was great progress in understanding actual molecular mechanisms in biology, and in figuring out how genetic and developmental processes work. But even as huge amounts of data accumulated, enthusiasm for large-scale “theories of biology” (that might for example address the production of complexity in biological evolution) seemed to wane. (The discipline of systems biology attempted to develop specific, usually mathematical, models for biological systems—but there never emerged much in the way of overarching theoretical principles, except perhaps, somewhat specifically, in areas like immunology and neuroscience.)

One significant exception in terms of fundamental theory was Greg Chaitin’s concept from around 2010 of “metabiology”: an effort (see below) to use ideas from the theory of computation to understand very general features of the evolution of programs and relate them to biological evolution.

Starting in the 1950s another strand of development (sometimes viewed as a practical branch of artificial intelligence) involved the idea of “machine learning”. Genetic algorithms were one of half a dozen common approaches. Another was based on artificial neural nets. For decades machine learning languished as a somewhat esoteric field, dominated by engineering solutions that would occasionally deliver specific application results. But then in 2011 there was unexpectedly dramatic success in using neural nets for image identification, followed in subsequent years by successes in other areas, and culminating in 2022 with the arrival of large language models and ChatGPT.

What hadn’t been anticipated was that the behavior of neural nets can change a lot if they’re given sufficiently huge amounts of training. But there isn’t any good understanding of just why this is so, and just how successful neural nets can be at what kinds of tasks. Ever since the 1940s it has been recognized that there are relations between biological evolution and learning in neural nets. And having now seen the impressive things neural nets can do, it seems worthwhile to look again at what happens in biological evolution—and to try to understand why it works, not least as a prelude to understanding more about neural nets and machine learning.

Personal Notes

It’s strange to say, but most of what I’ve done here I should really have done forty years ago. And I almost did. Except that I didn’t try quite the right experiments. And I didn’t have the intuition to think that it was worth trying more.

Forty years later, I have new intuition, particularly informed by experience with modern machine learning. But even now, what made possible what I’ve done here was a chance experiment done for a somewhat different purpose.

Back in 1981 I had become very interested in the question of how complexity arises in the natural world, and I was trying to come up with models that might capture this. Meanwhile, I had just finished Version 1.0 of SMP, the forerunner to Mathematica and the Wolfram Language—and I was wondering how one might generalize its pattern-matching paradigm to “general AI”.

As it happened, right around that time, neural nets gained some (temporary) popularity. And seeing them as potentially relevant to both my topics I started simulating them and trying to see what kind of general theory I could develop about them. But I found them frustrating to work with. There seemed to be too many parameters and details to get any clear conclusions. And, at a practical level, I couldn’t get them to do anything particularly useful.

I decided that for my science question I needed to come up with something much simpler. And as a kind of minimal merger of spin systems and neural nets I ended up inventing cellular automata (only later did I discover that versions of them had been invented several times before).

As soon as I started doing experiments on them, I discovered that cellular automata were a window into an amazing new scientific world—that I have continued to explore in one way or another ever since. My key methodology, at least at first, was just to enumerate the simplest possible cellular automaton rules, and see what they did. The diversity—and complexity—of their behavior was remarkable. But the simplicity of the rules meant that the details of “successive rules” were usually fairly different—and while there were common themes in their overall behavior, there didn’t seem to be any particular structure to “rule space”. (Occasionally, though, particularly in finding examples for exposition, I would look at slightly more complicated and “multicolored” rules, and I certainly anecdotally noticed that rules with nearby rule numbers often had definite similarities in their behavior.)

It so happened that around the time I started publishing about cellular automata in 1983 there was a fair amount of ambient interest in theoretical biology. And (perhaps in part because of the “cellular” in “cellular automata”) I was often invited to theoretical biology conferences. People would sometimes ask about adaptation in cellular automata, and I would usually just emphasize what individual cellular automata could do, without any adaptation, and what significance it might have for the development of organisms.

But in 1985 I was going to a conference (at Los Alamos) on “Evolution, Games and Learning” and I decided I should take a look at the relation of these topics to cellular automata. But, too quickly, I segued away from investigating adaptation to trying to see what kind of pattern matching and other operations cellular automata might be able to be explicitly set up to do:

Many aspects of this paper still seem quite modern (and in fact should probably be investigated more now!). But—even though I absolutely had the tools to do it—I simply failed at that time to explore what I’ve now explored here.

Back in 1984 Problem 7 in my “Twenty Problems in the Theory of Cellular Automata” was “How is different behavior distributed in the space of cellular automaton rules?” And over the years I’d occasionally think about “cellular automaton rule space”, wondering, for example, what kind of geometry it might have, particularly in the continuum limit of infinitely large rules.

By the latter half of the 1980s “theoretical biology” conferences had segued to “artificial life” ones. And when I went to such conferences I was often frustrated. People would show me simulations that seemed to have far too many parameters to ever be able to conclude much. People would also often claim that natural selection was a “very simple theory”, but as soon as it was “implemented” there’d be all kinds of issues—and choices to be made—about population sizes, fitness cutoffs, interactions between organisms, and so on. And the end result was usually a descent into some kind of very specific simulation without obvious robust implications.

(In the mid-1980s I put a fair amount of effort into developing both the content and the organization of a new direction in science that I called “complex systems research”. My emphasis was on systems—like cellular automata—that had definite simple rules but highly complex behavior. Gradually, though, “complexity” started to be a popular general buzzword, and—I suspect partly to distinguish themselves from my efforts—some people started emphasizing that they weren’t just studying complex systems, they were studying complex adaptive systems. But all too often this seemed mostly to provide an excuse to dilute the clarity of what could be studied—and I was sufficiently put off that I paid very little attention.)

By the mid-1990s, I was in the middle of writing A New Kind of Science, and I wanted to use biology as an example application of my methodology and discoveries in the computational universe. In a section entitled “Fundamental Issues in Biology” I argued (as I have here) that computational irreducibility is a fundamentally stronger force than natural selection, and that when we see complexity in biology it’s most likely of “computational origin” rather than being “sculpted” by natural selection. And as part of that discussion, I included a picture of the “often-somewhat-gradual changes” in behavior that one sees with successive 1-bit changes in a k = 3, r = 1 cellular automaton rule (yes, the book was not in color):

This wasn’t done adaptively; it was basically just looking along a “random straight line” in rule space. And indeed both here and in most of the book, I was concerned with what systems like cellular automata “naturally do”, not what they can be constructed (or adaptively evolved) to do. I did give “constructions” of how cellular automata can perform particular computational tasks (like generating primes), and, somewhat obscurely, in a section on “Intelligence in the Universe” I explored finding k = 3, r = 1 rules that can successfully “double their input” (my reason for discussing these rules was to highlight the difficulty of saying whether one of these cellular automata was “constructed for a purpose” or was just “doing what it does”):

Many years went by. There’d be an occasional project at our Summer School about rule space, and occasionally about adaptation. I maintained an interest in foundational questions in biology, gradually collecting information and sometimes giving talks about the subject. Meanwhile—though I didn’t particularly internalize the connection then—by the mid-2010s, through our practical work on it in the Wolfram Language, I’d gotten quite up to speed with modern machine learning. Around the same time I also heard from my friend Greg Chaitin about his efforts (as he put it) to “prove Darwin” using the kind of computational ideas he’d applied in thinking about the foundations of mathematics.

Then in 2020 came our Physics Project, with its whole formalism around things like multiway graphs. It didn’t take long to realize that, yes, what I was calling “multicomputation” wasn’t just relevant for fundamental physics; it was something quite general that could be applied in many areas, which by 2021 I was trying to catalog:

I did some thinking about each of these. The one I tackled most seriously first was metamathematics, about which I finished a book in 2022. Late that year I was finishing a (50-year-in-gestation) project—informed by our Physics Project—on understanding the Second Law of thermodynamics, and as part of this I made what I thought was some progress on thinking about the fundamental character of biological systems (though not their adaptive evolution).

And then ChatGPT arrived. And in addition to being involved with it technologically, I started to think about the science of it, and particularly about how it could work. Part of it seemed to have to do with unrecognized regularities in human language, but part of it was a reflection of the emerging “meta discovery” that somehow if you “bashed” a machine learning system hard enough, it seemed like it could manage to learn almost anything.

But why did this work? At first I thought it must just be an “obvious” consequence of high dimensionality. But I soon realized there was more to it. And as part of trying to understand the boundaries of what’s possible I ended up a couple of months ago writing a piece exploring “Can AI Solve Science?”:

I talked about different potential objectives for science (making predictions, generating narrative explanations, etc.) And deep inside the piece I had a section entitled “Exploring Spaces of Systems” in which I talked about science problems of the form “Can one find a system that does X?”—and asked whether systems like neural nets could somehow let one “jump ahead” in what would otherwise be huge exhaustive searches. As a sideshow to this I thought it might be interesting to compare with what a non-neural-net adaptive evolution process could do.

Remembering Greg Chaitin’s ideas about connecting the halting problem to biological evolution I wondered if perhaps one could just adaptively evolve cellular automaton rules to find ones that generated a pattern with a particular finite lifetime. I imagined it as a classic machine learning problem, with a “loss function” one needed to minimize.

And so it was that just after 1 am on February 22 I wrote three lines of Wolfram Language code—and tried the experiment:

And it worked! I managed to find cellular automaton rules that would generate patterns living exactly 50 steps:

In retrospect, I was slightly lucky. First, that this ended up being such a simple experiment to try (at least in the Wolfram Language) that I did it even though I didn’t really expect it to work. And second, that for my very first experiment I picked parameters that happened to immediately work (k = 4, lifetime 50, etc.).

But, yes, I could in principle have done the same experiment 40 years ago, though without the Wolfram Language it wouldn’t have been so easy. Still, the computers I had back then were powerful enough that I could in principle have generated the same results then as now. But without my modern experience of machine learning I don’t think I would have tried—and I would certainly have given up too easily. And, yes, it’s a little humbling to realize that I’ve gone so many years assuming adaptive evolution was out of the reach of simple, clean experiments. But it’s satisfying now to be able to check off another mystery I’ve long wondered about. And to think that much more about the foundations of biology—and machine learning—might finally be within reach.

Thanks

Thanks to Brad Klee, Nik Murzin and Richard Assar for their help.

The specific results and ideas I’ve presented here are mostly very recent, but they build on background conversations I’ve had—some recently, some more than 40 years ago—with many people, including: Sydney Brenner, Greg Chaitin, Richard Dawkins, David Goldberg, Nigel Goldenfeld, Jack Good, Jonathan Gorard, Stephen J. Gould, Hyman Hartman, John Holland, Christian Jacob, Stuart Kauffman, Mark Kotanchek, John Koza, Chris Langton, Katja Della Libera, Aristid Lindenmayer, Pattie Maes, Bill Mydlowec, John Novembre, Pedro de Oliveira, George Oster, Norman Packard, Alan Perelson, Thomas Ray, Philip Rosedale, Robert Rosen, Terry Sejnowski, Brian Silverman, Karl Sims, John Maynard Smith, Catherine Wolfram, Christopher Wolfram and Elizabeth Wolfram.

The Importance of Multiway Systems

It’s all about systems where there can in effect be many possible paths of history. In a typical standard computational system like a cellular automaton, there’s always just one path, defined by evolution from one state to the next. But in a multiway system, there can be many possible next states—and thus many possible paths of history. Multiway systems have a central role in our Physics Project, particularly in connection with quantum mechanics. But what’s now emerging is that multiway systems in fact serve as a quite general foundation for a whole new “multicomputational” paradigm for modeling.

My objective here is twofold. First, I want to use multiway systems as minimal models for growth processes based on aggregation and tiling. And second, I want to use this concrete application as a way to develop further intuition about multiway systems in general. Elsewhere I have explored multiway systems for strings, multiway systems based on numbers, multiway Turing machines, multiway combinators, multiway expression evaluation and multiway systems based on games and puzzles. But in studying multiway systems for aggregation and tiling, we’ll be dealing with something that is immediately more physical and tangible.

When we think of “growth by aggregation” we typically imagine a “random process” in which new pieces get added “at random” to something. But each of these “random possibilities” in effect defines a different path of history. And the concept of a multiway system is to capture all those possibilities together. In a typical random (or “stochastic”) model one’s just tracing a single path of history, and one imagines one doesn’t have enough information to say which path it will be. But in a multiway system one’s looking at all the paths. And in doing so, one’s in a sense making a model for the “whole story” of what can happen.

The choice of a single path can be “nondeterministic”. But the whole multiway system is deterministic. And by studying that “deterministic whole” it’s often possible to make useful, quite general statements.

One can think of a particular moment in the evolution of a multiway system as giving something like an ensemble of states of the kind studied in statistical mechanics. But the general concept of a multiway system, with its discrete branching at discrete steps, depends on a level of fundamental discreteness that’s quite unfamiliar from traditional statistical mechanics—though is perfectly straightforward to define in a computational, or even mathematical, way.

For aggregation it’s easy enough to set up a minimal discrete model—at least if one allows explicit randomness in the model. But a major point of what we’ll do here is to “go above” that randomness, setting up our model in terms of a whole, deterministic multiway system.

What can we learn by looking at this whole multiway system? Well, for example, we can see whether there’ll always be growth—whatever the random choices may be—or whether the growth will sometimes, or even always, stop. And in many practical applications (think, for example, tumors) it can be very important to know whether growth always stops—or through what paths it can continue.

A lot of what we’ll at first do here involves seeing the effect of local constraints on growth. Later on, we’ll also look at effects of geometry, and we’ll study how objects of different shapes can aggregate, or ultimately tile.

The models we’ll introduce are in a sense very minimal—combining the simplest multiway structures with the simplest spatial structures. And with this minimality it’s almost inevitable that the models will show up as idealizations of all sorts of systems—and as foundations for good models of these systems.

At first, multiway systems can seem rather abstract and difficult to grasp—and perhaps that’s inevitable given our human tendency to think sequentially. But by seeing how multiway systems play out in the concrete case of growth processes, we get to build our intuition and develop a more grounded view—that will stand us in good stead in exploring other applications of multiway systems, and in general in coming to terms with the whole multicomputational paradigm.

The Simplest Case

It’s the ultimate minimal model for random discrete growth (often called the Eden model). On a square grid, start with one black cell, then at each step randomly attach a new black cell somewhere onto the growing “cluster”:

After 10,000 steps we might get:

But what are all the possible things that can happen? For that, we can construct a multiway system:

A lot of these clusters differ only by a trivial translation; canonicalizing by translation we get

or after another step:

If we also reduce out rotations and reflections we get

or after another step:

The set of possible clusters after t steps are just the possible polyominoes (or “square lattice animals”) with t cells. The number of these for successive t is

growing roughly like k^t for large t, with k a little larger than 4:

By the way, canonicalization by translation always reduces the number of possible clusters by a factor of t. Canonicalization by rotation and reflection can reduce the number by a factor of 8 if the cluster has no symmetry (which for large clusters becomes increasingly likely), and by a smaller factor the more symmetry the cluster has, as in:

With canonicalization, the multiway graph after 7 steps has the form

and it doesn’t look any simpler with alternative rendering:

If we imagine that at each step, cells are added with equal probability at every possible position on the cluster, or equivalently that all outgoing edges from a given cluster in the uncanonicalized multiway graph are followed with equal probability, then we can get a distribution of probabilities for the distinct canonical clusters obtained—here shown after 7 steps:

One feature of the large random cluster we saw at the beginning is that it has some holes in it. Clusters with holes start developing after 7 steps, with the smallest being:

This cluster can be reached through a subset of the multiway system:

And in fact in the limit of large clusters, the probability for there to be a hole seems to approach 1—even though the total fraction of area covered by holes approaches 0.

One way to characterize the “space of possible clusters” is to create a branchial graph by connecting every pair of clusters that have a common ancestor one step back in the multiway graph:

The connectedness of all these graphs reflects the fact that with the rule we’re using, it’s always possible at any step to go from one cluster to another by a sequence of delete-one-cell/add-one-cell changes.

The branchial graphs here also show a 4-fold symmetry resulting from the symmetry of the underlying lattice. Canonicalizing the states, we get smaller branchial graphs that no longer show any such symmetry:

Totalistically Constrained Growth (4-Cell Neighborhoods)

With the rule we’ve been discussing so far, a new cell to be attached can be anywhere on a cluster. But what if we limit growth, by requiring that new cells must have certain numbers of existing cells around them? Specifically, let’s consider rules that look at the neighbors around any given position, and allow a new cell there only if there are specified numbers of existing cells in the neighborhood.

Starting with a cross of black cells, here are some examples of random clusters one gets after 20 steps with all possible rules of this type (the initial “4” designates that these are 4-neighbor rules):

Rules that don’t allow new cells to end up with just one existing neighbor can only fill in corners in their initial conditions, and can’t grow any further. But any rule that allows growth with only one existing neighbor produces clusters that keep growing forever. And here are some random examples of what one can get after 10,000 steps:

The last of these is the unconstrained (Eden model) rule we already discussed above. But let’s look more carefully at the first case—where there’s growth only if a new cell will end up with exactly one neighbor. The canonicalized multiway graph in this case is:

The possible clusters here correspond to polyominoes that are “always one cell wide” (i.e. have no 2×2 blocks), or, equivalently, have perimeter 2t + 2 at step t. The number of such canonicalized clusters grows like:

This is an increasing fraction of the total number of polyominoes—implying that most large polyominoes take this “spindly” form.

A new feature of a rule with constraints is that not all locations around a cluster may allow growth. Here is a version of the multiway system above, with cells around each cluster annotated with green if new growth is allowed there, and red if it never can be:

In a larger random cluster, we can see that with this rule, most of the interior is “dead” in the sense that the constraint of the rule allows no further growth there:

By the way, the clusters generated by this rule can always be directly represented by their “skeleton graphs”:

Looking at random clusters for all the (grow-with-1-neighbor) rules above, we see different patterns of holes in each case:

There are altogether five types of cells being distinguished here, reflecting different neighbor configurations:

Here’s a sample cluster generated with the 4:{1,3} rule:

Cells indicated with already have too many neighbors, and so can never be added to the cluster. Cells indicated with have exactly the right number of neighbors to be added immediately. Cells indicated with don’t currently have the right number of neighbors to grow, but if neighbors are filled in, they might be able to be added. Sometimes it will turn out that when neighbors of cells get filled in, they will actually prevent the cell from being added (so that it becomes )—and in the particular case shown here that happens with the 2×2 blocks of cells.

The multiway graphs from the rules shown here are all qualitatively similar, but there are detailed differences. In particular, at least for many of the rules, an increasing number of states are “missing” relative to what one gets with the grow-in-all-cases 4:{1,2,3,4} rule—or, in other words, there are an increasing number of polyominoes that can’t be generated given the constraints:

The first polyomino that can’t be reached (which occurs at step 4) is:

At step 6 the polyominoes that can’t be reached for rules 4:{1,3} and 4:{1,3,4} are

while for 4:{1} and 4:{1,4} the additional polyomino

can also not be reached.

At step 8, the polyomino

is reachable with 4:{1} and 4:{1,3} but not with 4:{1,4} and 4:{1,3,4}.

Of some note is that none of the rules that exclude polyominoes can reach:

Totalistically Constrained Growth (8-Cell Neighborhoods)

What happens if one considers diagonal as well orthogonal neighbors, giving a total of 8 neighbors around a cell? There are 256 possible rules in this case, corresponding to the possible subsets of Range[8]. Here are samples of what they do after 200 steps, starting from an initial cluster:

Two cases that at least initially show growth here are (the “8” designates that these are 8-neighbor rules):

In the {2} case, the multiway graph begins with:

One might assume that every branch in this graph would continue forever, and that growth would never “get stuck”. But it turns out that after 9 steps the following cluster is generated:

And with this cluster, no further growth is possible: no positions around the boundary have exactly 2 neighbors. In the multiway graph up to 10 steps, it turns out this is the only “terminal cluster” that can be generated—out of a total of 1115 possible clusters:

So how is that terminal cluster reached? Here’s the fragment of multiway graph that leads to it:

If we don’t prune off all the ways to “go astray”, the fragment appears as part of a larger multiway graph:

And if one follows all paths in the unpruned (and uncanonicalized) multiway graph at random (i.e. at each step, one chooses each branch with equal probability), it turns out that the probability of ever reaching this particular terminal cluster is just:

(And the fact that this number is fairly small implies that the system is far from confluent; there are many paths that, for example, don’t converge to the fixed point corresponding to this terminal cluster.)

If we keep going in the evolution of the multiway system, we’ll reach other terminal clusters; after 12 steps the following have appeared:

For the {3} rule above, the multiway system takes a little longer to “get going”:

Once again there are terminal clusters where the system gets stuck; the first of them appears at step 14:

And also once again the terminal cluster appears as an isolated node in the whole multiway system:

The fragment of multiway graph that leads to it is:

So far we’ve been finding terminal clusters by waiting for them to appear in the evolution of the multiway system. But there’s another approach, similar to what one might use in filling in something like a tiling. The idea is that every cell in a terminal cluster must have neighbors that don’t allow further growth. In other words, the terminal cluster must consist of certain “local tiles” for which the constraints don’t allow growth. But what configurations of local tiles are possible? To determine this, we turn the matching conditions for the tiles into logical expressions whose variables are True and False depending on whether particular positions in the template do or do not contain cells in the cluster. By solving the satisfiability problem for the combination of these logical expressions, one finds configurations of cells that could conceivably correspond to terminal clusters.

Following this procedure for the {2} rules with regions of up to 6×6 cells we find:

But now there’s an additional constraint. Assuming one starts from a connected initial cluster, any subsequent cluster generated must also be connected. Removing the non-connected cases we get:

So given these terminal clusters, what initial conditions can lead to them? To determine this we effectively have to invert the aggregation process—giving in the end a multiway graph that includes all initial conditions that can generate a given terminal cluster. For the smallest terminal cluster we get:

Our 4-cell “T” initial condition appears here—but we see that there are also even smaller 2-cell initial conditions that lead to the same terminal cluster.

For all the terminal clusters we showed before, we can construct the multiway graphs starting with the minimal initial clusters that lead to them:

For terminal clusters like

there’s no nontrivial multiway system to show, since these clusters can only appear as initial conditions; they can never be generated in the evolution.

There are quite a few small clusters that can only appear as initial conditions, and do not have preimages under the aggregation rule. Here are the cases that fit in a 3×3 region:

The case of the {3} rule is fairly similar to the {2} rule. The possible terminal clusters up to 5×5 are:

However, most of these have only a fairly limited set of possible preimages:

For example we have:

And indeed beyond the (size-17) example we already showed above, no other terminal clusters that can be generated from a T initial condition appear here. Sampling further, however, additional terminal clusters appear (beginning at size 25):

The fragments of multiway graphs for the first few of these are:

Random Evolution

We’ve seen above that for the rules we’ve been investigating, terminal clusters are quite rare among possible states in the multiway system. But what happens if we just evolve at random? How often will we wind up with a terminal cluster? When we say “evolve at random”, what we mean is that at each step we’re going to look at all possible positions where a new cell could be added to the cluster that exists so far, and then we’re going to pick with equal probability at which of these to actually add the new cell.

For the 8:{3} rule something surprising happens. Even though terminal clusters are rare in its multiway graph, it turns out that regardless of its initial conditions, it always eventually reaches a terminal cluster—though it often takes a while. And here, for example, are a few possible terminal clusters, annotated with the number of steps it took to reach them (which is also equal to the number of cells they contain):

The distribution of the number of steps to termination seems to be very roughly exponential (here based on a sample of 10,000 random cases)—with mean lifetime around 2300 and half-life around 7400:

Here’s an example of a large terminal cluster—that takes 21,912 steps to generate:

And here’s a map showing when growth in different parts of this cluster occurred (with blue being earliest and red being latest):

This picture suggests that different parts of the cluster “actively grow” at different times, and if we look at a “spacetime” plot of where growth occurs as a function of time, we can confirm this:

And indeed what this suggests is that what’s happening is that different parts of the cluster are at first “fertile”, but later inevitably “burn out”—so that in the end there are no possible positions left where growth can occur.

But what shapes can the final terminal clusters form? We can get some idea by looking at a “compactness measure” (of the kind often used to study gerrymandering) that roughly gives the standard deviation of the distances from the center of each cluster to each of the cells in it. Both “very stringy” and “roughly circular” clusters are fairly rare; most clusters lie somewhere in between:

If we look not at the 8:{3} but instead at the 8:{2} rule, things are very different. Once again, it’s possible to reach a terminal cluster, as the multiway graph shows. But now random evolution almost never reaches a terminal cluster, and instead almost always “runs away” to generate an infinite cluster. The clusters generated in this case are typically much more “compact” than in the 8:{3} case

and this is also reflected in the “spacetime” version:

Parallel Growth and Causal Graphs

In building up our clusters so far, we’ve always been assuming that cells are added sequentially, one at a time. But if two cells are far enough apart, we can actually add them “simultaneously”, in parallel, and end up building the same cluster. We can think of the addition of each cell as being an “event” that updates the state of the cluster. Then—just like in our Physics Project, and other applications of multicomputation—we can define a causal graph that represents the causal dependencies between these events, and then foliations of this causal graph tell us possible overall sequences of updates, including parallel.

As an example, consider this sequence of states in the “always grow” 4:{1,2,3,4} rule—where at each step the cell that’s new is colored red (and we’re including the “nothing” state at the beginning):

Every transition between successive states defines an event:

There’s then causal dependence of one event on another if the cell added in the second event is adjacent to the one added in the first event. So, for example, there are causal dependencies like

and

where in the second case additional “spatially separated” cells have been added that aren’t involved in the causal dependence. Putting all the causal dependencies together, we get the complete causal graph for this evolution:

We can recover our original sequence of states by picking a particular ordering of these events (here indicated by the positions of the cells they add):

This path has the property that it always follows the direction of causal edges—and we can make that more obvious by using a different layout for the causal graph:

But in general we can use any ordering of events consistent with the causal graph. Another ordering (out of a total of 40,320 possibilities in this case) is

which gives the sequence of states

with the same final cluster configuration, but different intermediate states.

But now the point is that the constraints implied by the causal graph do not require all events to be applied sequentially. Some events can be considered “spacelike separated” and so can be applied simultaneously. And in fact, any foliation of the causal graph defines a certain sequence for applying events—either sequentially or in parallel. So, for example, here is one particular foliation of the causal graph (shown with two different renderings for the causal graph):

And here is the corresponding sequence of states obtained:

And since in some slices of this foliation multiple events happen “in parallel”, it’s “faster” to get to the final configuration. (As it happens, this foliation is like a “cosmological rest frame foliation” in our Physics Project, and involves the maximum possible number of events happening on each slice.)

Different foliations (and there are a total of 678,972 possibilities in this case) will give different sequences of states, but always the same final state:

Note that nothing we’ve done here depends on the particular rule we’ve used. So, for example, for the 8:{2} rule with sequence of states

the causal graph is:

It’s worth commenting that everything we’ve done here has been for particular sequences of states, i.e. particular paths in the multiway graph. And in effect what we’re doing is the analog of classical spacetime physics—tracing out causal dependencies in particular evolution histories. But in general we could look at the whole multiway causal graph, with events that are not only timelike or spacelike separated, but also branchlike separated. And if we make foliations of this graph, we’ll end up not only with “classical” spacetime states, but also “quantum” superposition states that would need to be represented by something like multispace (in which at each spatial position, there is a “branchial stack” of possible cell values).

The One-Dimensional Case

So far we’ve been considering aggregation processes in two dimensions. But what about one dimension? In 1D, a “cluster” just consists of a sequence of cells. The simplest rule allows a cell to be added whenever it’s adjacent to a cell that’s already there. Starting from a single cell, here’s a possible random evolution according to such a rule, shown evolving down the page:

We can also construct the multiway system for this rule:

Canonicalizing the states gives the trivial multiway graph:

But just like in the 2D case things get less trivial if there are constraints on growth. For example, assume that before placing a new cell we count the number of cells that lie either distance 1 or distance 2 away. If the number of allowed cells can only be exactly 1 we get behavior like:

The corresponding multiway system is

or after canonicalization:

The number of distinct sequences after t steps here is given by

which can be expressed in terms of Fibonacci numbers, and for large t is about .

The rule in effect generates all possible Morse-code-like sequences, consisting of runs of either 2-cell (“long”) black blocks or 1-cell (“short”) black blocks, interspersed by “gaps” of single white cells.

The branchial graphs for this system have the form:

Looking at random evolutions for all possible rules of this type we get:

The corresponding canonicalized multiway graphs are:

The rules we’ve looked at so far are purely totalistic: whether a new cell can be added depends only on the total number of cells in its neighborhood. But (much like, for example, in cellular automata) it’s also possible to have rules where whether one can add a new cell depends on the complete configuration of cells in a neighborhood. Mostly, however, such rules seem to behave very much like totalistic ones.

Other generalizations include, for example, rules with multiple “colors” of cells, and rules that depend either on the total number of cells of different colors, or their detailed configurations.

The Three-Dimensional Case

The kind of analysis we’ve done for 2D and 1D aggregation systems can readily be extended to 3D. As a first example, consider a rule in which cells can be added along each of the 6 coordinate directions in a 3D grid whenever they are adjacent to an existing cell. Here are some typical examples of random clusters formed in this case:

Taking successive slices through the first of these (and coloring by “age”) we get:

If we allow a cell to be added only when it is adjacent to just one existing cell (corresponding to the rule 6:{1}) we get clusters that from the outside look almost indistinguishable

but which have an “airier” internal structure:

Much like in 2D, with 6 neighbors, there can’t be unbounded growth unless cells can be added when there is just one cell in the neighborhood. But in analogy to what happens in 2D, things get more complicated when we allow “corner adjacency” and have a 26-cell neighborhood.

If cells can be added whenever there’s at least one adjacent cell, the results are similar to the 6-neighbor case, except that now there can be “corner-adjacent outgrowths”

and the whole structure is “still airier”:

Little qualitatively changes for a rule like 26:{2} where growth can occur only with exactly 2 neighbors (here starting with a 3D dimer):

But the general question of when there is growth, and when not, is quite complicated and subtle. In particular, even with a specific rule, there are often some initial conditions that can lead to unbounded growth, and others that cannot.

Sometimes there is growth for a while, but then it stops. For example, with the rule 26:{9}, one possible path of evolution from a 3×3×3 block is:

The full multiway graph in this case terminates, confirming that no unbounded growth is ever possible:

With other initial conditions, however, this rule can grow for longer (here shown every 10 steps):

And from what one can tell, all rules 26:{n} lead to unbounded growth for , and do not for .

Polygonal Shapes

So far, we’ve been looking at “filling in cells” in grids—in 2D, 1D and 3D. But we can also look at just “placing tiles” without a grid, with each new tile attaching edge to edge to an existing tile.

For square tiles, there isn’t really a difference:

And the multiway system is just the same as for our original “grow anywhere” rule on a 2D grid:

Here’s now what happens for triangular tiles:

The multiway graph now generates all polyiamonds (triangular polyforms):

And since equilateral triangles can tessellate in a regular lattice, we can think of this—like the square case—as “filling in cells in a lattice” rather than just “placing tiles”. Here are some larger examples of random clusters in this case:

Essentially the same happens with regular hexagons:

The multiway graph generates all polyhexes:

Here are some examples of larger clusters—showing somewhat more “tendrils” than the triangular case:

And in an “effectively lattice” case like this we could also go on and impose constraints on neighborhood configurations, much as we did in earlier sections above.

But what happens if we consider shapes that do not tessellate the plane—like regular pentagons? We can still “sequentially place tiles” with the constraint that any new tile can’t overlap an existing one. And with this rule we get for example:

Here are some “randomly grown” larger clusters—showing all sorts of irregularly shaped interstices inside:

(And, yes, generating such pictures correctly is far from trivial. In the “effectively lattice” case, coincidences between polygons are fairly easy to determine exactly. But in something like the pentagon case, doing so requires solving equations in a high-degree algebraic number field.)

The multiway graph, however, does not show any immediately obvious differences from the ones for “effectively lattice” cases:

It makes it slightly easier to see what’s going on if we riffle the results on the last step we show:

The branchial graphs in this case have the form:

Here’s a larger cluster formed from pentagons:

And remember that the way this is built is sequentially to add one pentagon at each step by testing every “exposed edge” and seeing in which cases a pentagon will “fit”. As in all our other examples, there is no preference given to “external” versus “internal” edges.

Note that whereas “effectively lattice” clusters always eventually fill in all their holes, this isn’t true for something like the pentagon case. And in this case it appears that in the limit, about 28% of the overall area is taken up by holes. And, by the way, there’s a definite “zoo” of at least small possible holes, here plotted with their (logarithmic) probabilities:

So what happens with other regular polygons? Here’s an example with octagons (and in this case the limiting total area taken up by holes is about 35%):

And, by the way, here’s the “zoo of holes” in this case:

With pentagons, it’s pretty clear that difficult-to-resolve geometrical situations will arise. And one might have thought that octagons would avoid these. But there are still plenty of strange “mismatches” like

that aren’t easy to characterize or analyze. By the way, one should note that any time a “closed hole” is formed, the vectors corresponding to the edges that form its boundary must sum to zero—in effect defining an equation.

When the number of sides in the regular polygon gets large, our clusters will approximate circle packings. Here’s an example with 12-gons:

But of course because we’re insisting on adding one polygon at a time, the resulting structure is much “airier” than a true circle packing—of the kind that would be obtained (at least in 2D) by “pushing on the edges” of the cluster.

Polyomino Tilings

In the previous section we considered “sequential tilings” constructed from regular polygons. But the methods we used are quite general, and can be applied to sequential tilings formed from any shape—or shapes (or, at least, any shapes for which “attachment edges” can be identified).

As a first example, consider a domino or dimer shape—which we assume can be oriented both vertically and horizontally:

Here’s a somewhat larger cluster formed from dimers:

Here’s the canonicalized multiway graph in this case:

And here are the branchial graphs:

So what about other polyomino shapes? What happens when we try to sequentially tile with these—effectively making “polypolyominoes”?

Here’s an example based on an L-shaped polyomino:

Here’s a larger cluster

and here’s the canonicalized multiway graph after just 1 step

and after 2 steps:

The only other 3-cell polyomino is the tromino:

(For dimers, the limiting fraction of area covered by holes seems to be about 17%, while for L and tromino polyominoes, it’s about 27%.)

Going to 4 cells, there are 5 possible polyominoes—and here are samples of random clusters that can be built with them (note that in the last case shown, we require only that “subcells” of the 2×2 polyomino must align):

The corresponding multiway graphs are:

Continuing for more steps in a few cases:

Some polyominoes are “more awkward” to fit together than others—so these typically give clusters of “lower density”:

So far, we’ve always considered adding new polyominoes so that they “attach” on any “exposed edge”. And the result is that we can often get long “tendrils” in our clusters of polyominoes. But an alternative strategy is to try to add polyominoes as “compactly” as possible, in effect by adding successive “rings” of polyominoes (with “older” rings here colored bluer):

In general there are many ways to add these rings, and eventually one will often get stuck, unable to add polyominoes without leaving holes—as indicated by the red annotation here:

Of course, that doesn’t mean that if one was prepared to “backtrack and try again”, one couldn’t find a way to extend the cluster without leaving holes. And indeed for the polyomino we’re looking at here it’s perfectly possible to end up with “perfect tilings” in which no holes are left:

In general, we could consider all sorts of different strategies for growing clusters by adding polyominoes “in parallel”—just like in our discussion of causal graphs above. And if we add polyominoes “a ring at a time” we’re effectively making a particular choice of foliation—in which the successive “ring states” turn out be directly analogous to what we call “generational states” in our Physics Project.

If we allow holes (and don’t impose other constraints), then it’s inevitable that—just with ordinary, sequential aggregation—we can grow an unboundedly large cluster of polyominoes of any shape, just by always attaching one edge of each new polyomino to an “exposed” edge of the existing cluster. But if we don’t allow holes, it’s a different story—and we’re talking about a traditional tiling problem, where there are ultimately cases where tiling is impossible, and only limited-size clusters can be generated.

As it happens, all polyominoes with 6 or fewer cells do allow infinite tilings. But with 7 cells the following do not:

It’s perfectly possible to grow random clusters with these polyominoes—but they tend not to be at all compact, and to have lots of holes and tendrils:

So what happens if we try to grow clusters in rings? Here are all the possible ways to “surround” the first of these polyominoes with a “single ring”:

And it turns out in every single case, there are edges (indicated here in red) where the cluster can’t be extended—thereby demonstrating that no infinite tiling is possible with this particular polyomino.

By the way, much like we saw with constrained growth on a grid, it’s possible to have “tiling regions” that can extend only a certain limited distance, then always get stuck.

It’s worth mentioning that we’ve considered here the case of single polyominoes. It’s also possible to consider being able to add a whole set of possible polyominoes—“Tetris style”.

Nonperiodic Tilings

We’ve looked at polyominoes—and shapes like pentagons—that don’t tile the plane. But what about shapes that can tile the plane, but only nonperiodically? As an example, let’s consider Penrose tiles. The basic shapes of these tiles are

though there are additional matching conditions (implicitly indicated by the arrows on each tile), which can be enforced either by putting notches in the tiles or by decorating the tiles:

Starting with these individual tiles, we can build up a multiway system by attaching tiles wherever the matching rules are satisfied (note that all edges of both tiles are the same length):

So how can we tell that these tiles can form a nonperiodic tiling? One approach is to generate a multiway system in which at successive steps we surround clusters with rings in all possible ways:

Continuing for another step we get:

Notice that here some of the branches have died out. But the question is what branches exist that will continue forever, and thus lead to an infinite tiling? To answer this we have to do a bit of analysis.

The first step is to see what possible “rings” can have formed around the original tile. And we can read all of these off from the multiway graph:

But now it’s convenient to look not at possible rings around a tile, but instead at possible configurations of tiles that can surround a single vertex. There turns out to be the following limited set:

The last two of these configurations have the feature that they can’t be extended: no tile can be added on the center of their “blue sides”. But it turns out that all the other configurations can be extended—though only to make a nested tiling, not a periodic one.

And a first indication of this is that larger copies of tiles (“supertiles”) can be drawn on top of the first three configurations we just identified, in such a way that the vertices of the supertiles coincide with vertices of the original tiles:

And now we can use this to construct rules for a substitution system:

Applying this substitution system builds up a nested tiling that can be continued forever:

But is such a nested tiling the only one that is possible with our original tiles? We can prove that it is by showing that every tile in every possible configuration occurs within a supertile. We can pull out possible configurations from the multiway system—and then in each case it turns out that we can indeed find a supertile in which the original tile occurs:

And what this all means is that the only infinite paths that can occur in the multiway system are ones that correspond to nested tilings; all other paths must eventually die out.

The Penrose tiling involves two distinct tiles. But in 2022 it was discovered that—if one’s allowed to flip the tile over—just a single (“hat”) tile is sufficient to force a nonperiodic tiling:

The full multiway graph obtained from this tile (and its flip-over) is complicated, but many paths in it lead (at least eventually) to “dead ends” which cannot be further extended. Thus, for example, the following configurations—which appear early in the multiway graph—all have the property that they can’t occur in an infinite tiling:

In the first case here, we can successively add a few rings of tiles:

But after 7 rings, there is a “contradiction” on the boundary, and no further growth is possible (as indicated by the red annotations):

Having eliminated cases that always lead to “dead ends” the resulting simplified multiway graph effectively includes all joins between hat tiles that can ultimately lead to surviving configurations:

Once again we can define a supertile transformation

where the region outlined in red can potentially overlap another supertile. Now we can construct a multiway graph for the supertile (in its “bitten out” and full variant)

and can see that there is a (one-to-one) map from the multiway graph for the original tiles and for these supertiles:

And now from this we can tell that there can be arbitrarily large nested tilings using the hat tile:

Personal Notes

Tucked away on page 979 of my 2002 book A New Kind of Science is a note (written in 1995) on “Generalized aggregation models”:

And in many ways the current piece is a three-decade-later followup to that note—using a new approach based on multiway systems.

In A New Kind of Science I did discuss multiway systems (both abstractly, and in connection with fundamental physics). But what I said about aggregation was mostly in a section called “The Phenomenon of Continuity” which discussed how randomness could on a large scale lead to apparent continuity. That section began by talking about things like random walks, but went on to discuss the same minimal (“Eden model”) example of “random aggregation” that I give here. And then, in an attempt to “spruce up” my discussion of aggregation, I started looking at “aggregation with constraints”. In the main text of the book I gave just two examples:

But then for the footnote I studied a wider range of constraints (enumerating them much as I had cellular automata)—and noticed the surprising phenomenon that with some constraints the aggregation process could end up getting stuck, and not being able to continue.

For years I carried around the idea of investigating that phenomenon further. And it was often on my list as a possible project for a student to explore at the Wolfram Summer School. Occasionally it was picked, and progress was made in various directions. And then a few years ago, with our Physics Project in the offing, the idea arose of investigating it using multiway systems—and there were Summer School projects that made progress on this. Meanwhile, as our Physics Project progressed, our tools for working with multiway systems greatly improved—ultimately making possible what we’ve done here.

By the way, back in the 1990s, one of the many topics I studied for A New Kind of Science was tilings. And in an effort to determine what tilings were possible, I investigated what amounts to aggregation under tiling constraints—which is in fact even a generalization of what I consider here:

Thanks

First and foremost, I’d like to thank Brad Klee for extensive help with this piece, as well as Nik Murzin for additional help. (Thanks also to Catherine Wolfram, Christopher Wolfram and Ed Pegg for specific pointers.) I’d like to thank various Wolfram Summer School students (and their mentors) who’ve worked on aggregation systems and their multiway interpretation in recent years: Kabir Khanna 2019 (mentors: Christopher Wolfram & Jonathan Gorard), Lina M. Ruiz 2021 (mentors: Jesse Galef & Xerxes Arsiwalla), Pietro Pepe 2023 (mentor: Bob Nachbar). (Also related are the Summer School projects on tilings by Bowen Ping 2023 and Johannes Martin 2023.)

See Also

Games and Puzzles as Multicomputational Systems

The Physicalization of Metamathematics and Its Implications for the Foundations of Mathematics

Multicomputation with Numbers: The Case of Simple Multiway Systems

Multicomputation: A Fourth Paradigm for Theoretical Science

Multiway Turing Machines

Combinators: A Centennial View—Updating Schemes and Multiway Systems

The Updating Process for String Substitution Systems

An Unexpected Correspondence

Enter any expression and it’ll get evaluated:

And internally—say in the Wolfram Language—what’s going on is that the expression is progressively being transformed using all available rules until no more rules apply. Here the process can be represented like this:

We can think of the yellow boxes in this picture as corresponding to “evaluation events” that transform one “state of the expression” (represented by a blue box) to another, eventually reaching the “fixed point” 12.

And so far this may all seem very simple. But actually there are many surprisingly complicated and deep issues and questions. For example, to what extent can the evaluation events be applied in different orders, or in parallel? Does one always get the same answer? What about non-terminating sequences of events? And so on.

I was first exposed to such issues more than 40 years ago—when I was working on the design of the evaluator for the SMP system that was the forerunner of Mathematica and the Wolfram Language. And back then I came up with pragmatic, practical solutions—many of which we still use today. But I was never satisfied with the whole conceptual framework. And I always thought that there should be a much more principled way to think about such things—that would likely lead to all sorts of important generalizations and optimizations.

Well, more than 40 years later I think we can finally now see how to do this. And it’s all based on ideas from our Physics Project—and on a fundamental correspondence between what’s happening at the lowest level in all physical processes and in expression evaluation. Our Physics Project implies that ultimately the universe evolves through a series of discrete events that transform the underlying structure of the universe (say, represented as a hypergraph)—just like evaluation events transform the underlying structure of an expression.

And given this correspondence, we can start applying ideas from physics—like ones about spacetime and quantum mechanics—to questions of expression evaluation. Some of what this will lead us to is deeply abstract. But some of it has immediate practical implications, notably for parallel, distributed, nondeterministic and quantum-style computing. And from seeing how things play out in the rather accessible and concrete area of expression evaluation, we’ll be able to develop more intuition about fundamental physics and about other areas (like metamathematics) where the ideas of our Physics Project can be applied.

Causal Graphs and Spacetime

The standard evaluator in the Wolfram Language applies evaluation events to an expression in a particular order. But typically multiple orders are possible; for the example above, there are three:

So what determines what orders are possible? There is ultimately just one constraint: the causal dependencies that exist between events. The key point is that a given event cannot happen unless all the inputs to it are available, i.e. have already been computed. So in the example here, the evaluation event cannot occur unless the one has already occurred. And we can summarize this by “drawing a causal edge” from the event to the one. Putting together all these “causal relations”, we can make a causal graph, which in the example here has the simple form (where we include a special “Big Bang” initial event to create the original expression that we’re evaluating):

What we see from this causal graph is that the events on the left must all follow each other, while the event on the right can happen “independently”. And this is where we can start making an analogy with physics. Imagine our events are laid out in spacetime. The events on the left are “timelike separated” from each other, because they are constrained to follow one after another, and so must in effect “happen at different times”. But what about the event on the right? We can think of this as being “spacelike separated” from the others, and happening at a “different place in space” asynchronously from the others.

As a quintessential example of a timelike chain of events, consider making the definition

and then generating the causal graph for the events associated with evaluating f[f[f[1]]] (i.e. Nest[f, 1, 3]):

A straightforward way to get spacelike events is just to “build in space” by giving an expression like f[1] + f[1] + f[1] that has parts that can effectively be thought of as being explicitly “laid out in different places”, like the cells in a cellular automaton:

But one of the major lessons of our Physics Project is that it’s possible for space to “emerge dynamically” from the evolution of a system (in that case, by successive rewriting of hypergraphs). And it turns out very much the same kind of thing can happen in expression evaluation, notably with recursively defined functions.

As a simple example, consider the standard definition of Fibonacci numbers:

With this definition, the causal graph for the evaluation of f[3] is then:

For f[5], dropping the “context” of each event, and showing only what changed, the graph is

while for f[8] the structure of the graph is:

So what is the significance of there being spacelike-separated parts in this graph? At a practical level, a consequence is that those parts correspond to subevaluations that can be done independently, for example in parallel. All the events (or subevaluations) in any timelike chain must be done in sequence. But spacelike-separated events (or subevaluations) don’t immediately have a particular relative order. The whole graph can be thought of as defining a partial ordering for all events—with the events forming a partially ordered set (poset). Our “timelike chains” then correspond to what are usually called chains in the poset. The antichains of the poset represent possible collections of events that can occur “simultaneously”.

And now there’s a deep analogy to physics. Because just like in the standard relativistic approach to spacetime, we can define a sequence of “spacelike surfaces” (or hypersurfaces in 3 + 1-dimensional spacetime) that correspond to possible successive “simultaneity surfaces” where events can consistently be done simultaneously. Put another way, any “foliation” of the causal graph defines a sequence of “time steps” in which particular collections of events occur—as in for example:

And just like in relativity theory, different foliations correspond to different choices of reference frames, or what amount to different choices of “space and time coordinates”. But at least in the examples we’ve seen so far, the “final result” from the evaluation is always the same, regardless of the foliation (or reference frame) we use—just as we expect when there is relativistic invariance.

As a slightly more complex—but ultimately very similar—example, consider the nestedly recursive function:

Now the causal graph for f[12] has the form

which again has both spacelike and timelike structure.

Foliations and the Definition of Time

Let’s go back to our first example above—the evaluation of (1 + (2 + 2)) + (3 + 4). As we saw above, the causal graph in this case is:

The standard Wolfram Language evaluator makes these events occur in the following order:

And by applying events in this order starting with the initial state, we can reconstruct the sequence of states that will be reached at each step by this particular evaluation process (where now we’ve highlighted in each state the part that’s going to be transformed at each step):

Here’s the standard evaluation order for the Fibonacci number f[3]:

And here’s the sequence of states generated from this sequence of events:

Any valid evaluation order has to eventually visit (i.e. apply) all the events in the causal graph. Here’s the path that’s traced out by the standard evaluation order on the causal graph for f[8]. As we’ll discuss later, this corresponds to a depth-first scan of the (directed) graph:

But let’s return now to our first example. We’ve seen the order of events used in the standard Wolfram Language evaluation process. But there are actually three different orders that are consistent with the causal relations defined by the causal graph (in the language of posets, each of these is a “total ordering”):

And for each of these orders we can reconstruct the sequence of states that would be generated:

Up to this point we’ve always assumed that we’re just applying one event at a time. But whenever we have spacelike-separated events, we can treat such events as “simultaneous”—and applied at the same point. And—just like in relativity theory—there are typically multiple possible choices of “simultaneity surfaces”. Each one corresponds to a certain foliation of our causal graph. And in the simple case we’re looking at here, there are only two possible (maximal) foliations:

From such foliations we can reconstruct possible total orderings of individual events just by enumerating possible permutations of events within each slice of the foliation (i.e. within each simultaneity surface). But we only really need a total ordering of events if we’re going to apply one event at a time. Yet the whole point is that we can view spacelike-separated events as being “simultaneous”. Or, in other words, we can view our system as “evolving in time”, with each “time step” corresponding to a successive slice in the foliation.

And with this setup, we can reconstruct states that exist at each time step—interspersed by updates that may involve several “simultaneous” (spacelike-separated) events. In the case of the two foliations above, the resulting sequences of (“reconstructed”) states and updates are respectively:

As a more complicated example, consider recursively evaluating the Fibonacci number f[3] as above. Now the possible (maximal) foliations are:

For each of these foliations we can then reconstruct an explicit “time series” of states, interspersed by “updates” involving varying numbers of events:

So where in all these is the standard evaluation order? Well, it’s not explicitly here—because it involves doing a single event at a time, while all the foliations here are “maximal” in the sense that they aggregate as many events as they can into each spacelike slice. But if we don’t impose this maximality constraint, are there foliations that in a sense “cover” the standard evaluation order? Without the maximality constraint, there turn out in the example we’re using to be not 10 but 1249 possible foliations. And there are 4 that “cover” the standard (“depth-first”) evaluation order (indicated by a dashed red line):

(Only the last foliation here, in which every “slice” is just a single event, can strictly reproduce the standard evaluation order, but the others are all still “consistent with it”.)

In the standard evaluation process, only a single event is ever done at a time. But what if instead one tries to do as many events as possible at a time? Well, that’s what our “maximal foliations” above are about. But one particularly notable case is what corresponds to a breadth-first scan of the causal graph. And this turns out to be covered by the very last maximal foliation we showed above.

How this works may not be immediately obvious from the picture. With our standard layout for the causal graph, the path corresponding to the breadth-first scan is:

But if we lay out the causal graph differently, the path takes on the much-more-obviously-breadth-first form:

And now using this layout for the various configurations of foliations above we get:

We can think of different layouts for the causal graph as defining different “coordinatizations of spacetime”. If the vertical direction is taken to be time, and the horizontal direction space, then different layouts in effect place events at different positions in time and space. And with the layout here, the last foliation above is “flat”, in the sense that successive slices of the foliation can be thought of as directly corresponding to successive “steps in time”.

In physics terms, different foliations correspond to different “reference frames”. And the “flat” foliation can be thought of as being like the cosmological rest frame, in which the observer is “at rest with respect to the universe”. In terms of states and events, we can also interpret this another way: we can say it’s the foliation in which in some sense the “largest possible number of events are being packed in at each step”. Or, more precisely, if at each step we scan from left to right, we’re doing every successive event that doesn’t overlap with events we’ve already done at this step:

And actually this also corresponds to what happens if, instead of using the built-in standard evaluator, we explicitly tell the Wolfram Language to repeatedly do replacements in expressions. To compare with what we’ve done above, we have to be a little careful in our definitions, using ⊕ and ⊖ as versions of + and – that have to get explicitly evaluated by other rules. But having done this, we get exactly the same sequence of “intermediate expressions” as in the flat (i.e. “breadth-first”) foliation above:

In general, different foliations can be thought of as specifying different “event-selection functions” to be applied to determine what events should occur at the next steps from any given state. At one extreme we can pick single-event-at-a-time event selection functions—and at the other extreme we can pick maximum-events-at-a-time event selection functions. In our Physics Project we have called the states obtained by applying maximal collections of events at a time “generational states”. And in effect these states represent the typical way we parse physical “spacetime”—in which we take in “all of space” at every successive moment of time. At a practical level the reason we do this is that the speed of light is somehow fast compared to the operation of our brains: if we look at our local surroundings (say the few hundred meters around us), light from these will reach us in a microsecond, while it takes our brains milliseconds to register what we’re seeing. And this makes it reasonable for us to think of there being an “instantaneous state of space” that we can perceive “all at once” at each particular “moment in time”.

But what’s the analog of this when it comes to expression evaluation? We’ll discuss this a little more later. But suffice it to say here that it depends on who or what the “observer” of the process of evaluation is supposed to be. If we’ve got different elements of our states laid out explicitly in arrays, say in a GPU, then we might again “perceive all of space at once”. But if, for example, the data associated with states is connected through chains of pointers in memory or the like, and we “observe” this data only when we explicitly follow these pointers, then our perception won’t as obviously involve something we can think of as “bulk space”. But by thinking in terms of foliations (or reference frames) as we have here, we can potentially fit what’s going on into something like space, that seems familiar to us. Or, put another way, we can imagine in effect “programming in a certain reference frame” in which we can aggregate multiple elements of what’s going on into something we can consider as an analog of space—thereby making it familiar enough for us to understand and reason about.

Multiway Evaluation and Multiway Graphs

We can view everything we’ve done so far as dissecting and reorganizing the standard evaluation process. But let’s say we’re just given certain underlying rules for transforming expressions—and then we apply them in all possible ways. It’ll give us a “multiway” generalization of evaluation—in which instead of there being just one path of history, there are many. And in our Physics Project, this is exactly how the transition from classical to quantum physics works. And as we proceed here, we’ll see a close correspondence between multiway evaluation and quantum processes.

But let’s start again with our expression (1 + (2 + 2)) + (3 + 4), and consider all possible ways that individual integer addition “events” can be applied to evaluate this expression. In this particular case, the result is pretty simple, and can be represented by a tree that branches in just two places:

But one thing to notice here is that even at the first step there’s an event that we’ve never seen before. It’s something that’s possible if we apply integer addition in all possible places. But when we start from the standard evaluation process, the basic event just never appears with the “expression context” we’re seeing it in here.

Each branch in the tree above in some sense represents a different “path of history”. But there’s a certain redundancy in having all these separate paths—because there are multiple instances of the same expression that appear in different places. And if we treat these as equivalent and merge them we now get:

(The question of “state equivalence” is a subtle one, that ultimately depends on the operation of the observer, and how the observer constructs their perception of what’s going on. But for our purposes here, we’ll treat expressions as equivalent if they are structurally the same, i.e. every instance of or of 5 is “the same” or 5.)

If we now look only at states (i.e. expressions) we’ll get a multiway graph, of the kind that’s appeared in our Physics Project and in many applications of concepts from it:

This graph in a sense gives a succinct summary of possible paths of history, which here correspond to possible evaluation paths. The standard evaluation process corresponds to a particular path in this multiway graph:

What about a more complicated case? For example, what is the multiway graph for our recursive computation of Fibonacci numbers? As we’ll discuss at more length below, in order to make sure every branch of our recursive evaluation terminates, we have to give a slightly more careful definition of our function f:

But now here’s the multiway tree for the evaluation of f[2]:

And here’s the corresponding multiway graph:

The leftmost branch in the multiway tree corresponds to the standard evaluation process; here’s the corresponding path in the multiway graph:

Here’s the structure of the multiway graph for the evaluation of f[3]:

Note that (as we’ll discuss more later) all the possible evaluation paths in this case lead to the same final expression, and in fact in this particular example all the paths are of the same length (12 steps, i.e. 12 evaluation events).

In the multiway graphs we’re drawing here, every edge in effect corresponds to an evaluation event. And we can imagine setting up foliations in the multiway graph that divide these events into slices. But what is the significance of these slices? When we did the same kind of thing above for causal graphs, we could interpret the slices as representing “instantaneous states laid out in space”. And by analogy we can interpret a slice in the multiway graph as representing “instantaneous states laid out across branches of history”. In the context of our Physics Project, we can then think of these slices as being like superpositions in quantum mechanics, or states “laid out in branchial space”. And, as we’ll discuss later, just as we can think of elements laid out in “space” as corresponding in the Wolfram Language to parts in a symbolic expression (like a list, a sum, etc.), so now we’re dealing with a new kind of way of aggregating states across branchial space, that has to be represented with new language constructs.

But let’s return to the very simple case of (1 + (2 + 2)) + (3 + 4). Here’s a more complete representation of the multiway evaluation process in this case, including both all the events involved, and the causal relations between them:

The “single-way” evaluation process we discussed above uses only part of this:

And from this part we can pull out the causal relations between events to reproduce the (“single-way”) causal graph we had before. But what if we pull out all the causal relations in our full graph?

What we then have is the multiway causal graph. And from foliations of this, we can construct possible histories—though now they’re multiway histories, with the states at particular time steps now being what amount to superposition states.

In the particular case we’re showing here, the multiway causal graph has a very simple structure, consisting essentially just of a bunch of isomorphic pieces. And as we’ll see later, this is an inevitable consequence of the nature of the evaluation we’re doing here, and its property of causal invariance (and in this case, confluence).

Branchlike Separation

Although what we’ve discussed has already been somewhat complicated, there’s actually been a crucial simplifying assumption in everything we’ve done. We’ve assumed that different transformations on a given expression can never apply to the same part of the expression. Different transformations can apply to different parts of the same expression (corresponding to spacelike-separated evaluation events). But there’s never been a “conflict” between transformations, where multiple transformations can apply to the same part of the same expression.

So what happens if we relax this assumption? In effect it means that we can generate different “incompatible” branches of history—and we can characterize the events that produce this as “branchlike separated”. And when such branchlike-separated events are applied to a given state, they’ll produce multiple states which we can characterize as “separated in branchial space”, but nevertheless correlated as a result of their “common ancestry”—or, in quantum mechanics terms, “entangled”.

As a very simple first example, consider the rather trivial function f defined by

If we evaluate f[f[0]] (for any f) there are immediately two “conflicting” branches: one associated with evaluation of the “outer f”, and one with evaluation of the “inner f”:

We can indicate branchlike-separated pairs of events by a dashed line:

Adding in causal edges, and merging equivalent states, we get:

We see that some events are causally related. The first two events are not—but given that they involve overlapping transformations they are “branchially related” (or, in effect, entangled).

Evaluating the expression f[f[0]+1] gives a more complicated graph, with two different instances of branchlike-separated events:

Extracting the multiway states graph we get

where now we have indicated “branchially connected” states by pink “branchial edges”. Pulling out only these branchial edges then gives the (rather trivial) branchial graph for this evaluation process:

There are many subtle things going on here, particularly related to the treelike structure of expressions. We’ve talked about separations between events: timelike, spacelike and branchlike. But what about separations between elements of an expression? In something like {f[0], f[0], f[0]} it’s reasonable to extend our characterization of separations between events, and say that the f[0]’s in the expression can themselves be considered spacelike separated. But what about in something like f[f[0]]? We can say that the f[_]’s here “overlap”—and “conflict” when they are transformed—making them branchlike separated. But the structure of the expression also inevitably makes them “treelike separated”. We’ll see later how to think about the relation between treelike-separated elements in more fundamental terms, ultimately using hypergraphs. But for now an obvious question is what in general the relation between branchlike-separated elements can be.

And essentially the answer is that branchlike separation has to “come with” some other form of separation: spacelike, treelike, rulelike, etc. Rulelike separation involves having multiple rules for the same object (e.g. a rule as well as )—and we’ll talk about this later. With spacelike separation, we basically get branchlike separation when subexpressions “overlap”. This is fairly subtle for tree-structured expressions, but is much more straightforward for strings, and indeed we have discussed this case extensively in connection with our Physics Project.

Consider the (rather trivial) string rewriting rule:

Applying this rule to AAAAAA we get:

Some of the events here are purely spacelike separated, but whenever the characters they involve overlap, they are also branchlike separated (as indicated by the dashed pink lines). Extracting the multiway states graph we get:

And now we get the following branchial graph:

So how can we see analogs in expression evaluation? It turns out that combinators provide a good example (and, yes, it’s quite remarkable that we’re using combinators here to help explain something—given that combinators almost always seem like the most obscure and difficult-to-explain things around). Define the standard S and K combinators:

Now we have for example

where there are many spacelike-separated events, and a single pair of branchlike + treelike-separated ones. With a slightly more complicated initial expression, we get the rather messy result

now with many branchlike-separated states:

Rather than using the full standard S, K combinators, we can consider a simpler combinator definition:

Now we have for example

where the branchial graph is

and the multiway causal graph is:

The expression f[f[f][f]][f] gives a more complicated multiway graph

and branchial graph:

Interpretations, Analogies and the Concept of Multi

Before we started talking about branchlike separation, the only kinds of separation we considered were timelike and spacelike. And in this case we were able to take the causal graphs we got, and set up foliations of them where each slice could be thought of as representing a sequential step in time. In effect, what we were doing was to aggregate things so that we could talk about what happens in “all of space” at a particular time.

But when there’s branchlike separation we can no longer do this. Because now there isn’t a single, consistent “configuration of all of space” that can be thought of as evolving in a single thread through time. Rather, there are “multiple threads of history” that wind their way through the branchings (and mergings) that occur in the multiway graph. One can make foliations in the multiway graph—much like one does in the causal graph. (More strictly, one really needs to make the foliations in the multiway causal graph—but these can be “inherited” by the multiway graph.)

In physics terms, the (single-way) causal graph can be thought of as a discrete version of ordinary spacetime—with a foliation of it specifying a “reference frame” that leads to a particular identification of what one considers space, and what time. But what about the multiway causal graph? In effect, we can imagine that it defines a new, branchial “direction”, in addition to the spatial direction. Projecting in this branchial direction, we can then think of getting a kind of branchial analog of spacetime that we can call branchtime. And when we construct the multiway graph, we can basically imagine that it’s a representation of branchtime.

A particular slice of a foliation of the (single-way) causal graph can be thought of as corresponding to an “instantaneous state of (ordinary) space”. So what does a slice in a foliation of the multiway graph represent? It’s effectively a branchial or multiway combination of states—a collection of states that can somehow all exist “at the same time”. And in physics terms we can interpret it as a quantum superposition of states.

But how does all this work in the context of expressions? The parts of a single expression like a + b + c + d or {a, b, c, d} can be thought of being spacelike separated, or in effect “laid out in space”. But what kind of a thing has parts that are “laid out in branchial space”? It’s a new kind of fundamentally multiway construct. We’re not going to explore it too much here, but in the Wolfram Language we might in future call it Multi. And just as {a, b, c, d} (or List[a, b, c, d]) can be thought of as representing a, b, c, d “laid out in space”, so now Multi[a, b, c, d] would represent a, b, c, d “laid out branchial space”.

In ordinary evaluation, we just generate a specific sequence of individual expressions. But in multiway evaluation, we can imagine that we generate a sequence of Multi objects. In the examples we’ve seen so far, we always eventually get a Multi containing just a single expression. But we’ll soon find out that that’s not always how things work, and we can perfectly well end up with a Multi containing multiple expressions.

So what might we do with a Multi? In a typical “nondeterministic computation” we probably want to ask: “Does the Multi contain some particular expression or pattern that we’re looking for?” If we imagine that we’re doing a “probabilistic computation” we might want to ask about the frequencies of different kinds of expressions in the Multi. And if we’re doing quantum computation with the normal formalism of quantum mechanics, we might want to tag the elements of the Multi with “quantum amplitudes” (that, yes, in our model presumably have magnitudes determined by path counting in the multiway graph, and phases representing the “positions of elements in branchial space”). And in a traditional quantum measurement, the concept would typically be to determine a projection of a Multi, or in effect an inner product of Multi objects. (And, yes, if one knows only that projection, it’s not going to be enough to let one unambiguously continue the “multiway computation”; the quantum state has in effect been “collapsed”.)

Is There Always a Definite Result?

For an expression like (1 + (2 + 2)) + (3 + 4) it doesn’t matter in what order one evaluates things; one always gets the same result—so that the corresponding multiway graph leads to just a single final state:

But it’s not always true that there’s a single final state. For example, with the definitions

standard evaluation in the Wolfram Language gives the result 0 for f[f[0]] but the full multiway graph shows that (with a different evaluation order) it’s possible instead to get the result g[g[0]]:

And in general when a certain collection of rules (or definitions) always leads to just a single result, one says that the collection of rules is confluent; otherwise it’s not. Pure arithmetic turns out to be confluent. But there are plenty of examples (e.g. in string rewriting) that are not. Ultimately a failure of confluence must come from the presence of branchlike separation—or in effect a conflict between behavior on two different branches. And so in the example above we see that there are branchlike-separated “conflicting” events that never resolve—yielding two different final outcomes:

As an even simpler example, consider the definitions and . In the Wolfram Language these definitions immediately overwrite each other. But assume they could both be applied (say through explicit , rules). Then there’s a multiway graph with two “unresolved” branches—and two outcomes:

For string rewriting systems, it’s easy to enumerate possible rules. The rule

(that effectively sorts the elements in the string) is confluent:

But the rule

is not confluent

and “evaluates” BABABA to four distinct outcomes:

These are all cases where “internal conflicts” lead to multiple different final results. But another way to get different results is through “side effects”. Consider first setting x = 0 then evaluating {x = 1, x + 1}:

If the order of evaluation is such that x + 1 is evaluated before x = 1 it will give 1, otherwise it will give 2, leading to the two different outcomes {1, 1} and {1, 2}. In some ways this is like the example above where we had two distinct rules: and . But there’s a difference. While explicit rules are essentially applied only “instantaneously”, an assignment like x = 1 has a “permanent” effect, at least until it is “overwritten” by another assignment. In an evaluation graph like the one above we’re showing particular expressions generated during the evaluation process. But when there are assignments, there’s an additional “hidden state” that in the Wolfram Language one can think of as corresponding to the state of the global symbol table. If we included this, then we’d again see rules that apply “instantaneously”, and we’d be able to explicitly trace causal dependencies between events. But if we elide it, then we effectively hide the causal dependence that’s “carried” by the state of the symbol table, and the evaluation graphs we’ve been drawing are necessarily somewhat incomplete.

Computations That Never End

The basic operation of the Wolfram Language evaluator is to keep doing transformations until the result no longer changes (or, in other words, until a fixed point is reached). And that’s convenient for being able to “get a definite answer”. But it’s rather different from what one usually imagines happens in physics. Because in that case we’re typically dealing with things that just “keep progressing through time”, without ever getting to any fixed point. (“Spacetime singularities”, say in black holes, do for example involve reaching fixed points where “time has come to an end”.)

But what happens in the Wolfram Language if we just type , without giving any value to ? The Wolfram Language evaluator will keep evaluating this, trying to reach a fixed point. But it’ll never get there. And in practice it’ll give a message, and (at least in Version 13.3 and above) return a TerminatedEvaluation object:

What’s going on inside here? If we look at the evaluation graph, we can see that it involves an infinite chain of evaluation events, that progressively “extrude” +1’s:

A slightly simpler case (that doesn’t raise questions about the evaluation of Plus) is to consider the definition

which has the effect of generating an infinite chain of progressively more “f-nested” expressions:

Let’s say we define two functions:

Now we don’t just get a simple chain of results; instead we get an exponentially growing multiway graph:

In general, whenever we have a recursive definition (say of f in terms of f or x in terms of x) there’s the possibility of an infinite process of evaluation, with no “final fixed point”. There are of course specific cases of recursive definitions that always terminate—like the Fibonacci example we gave above. And indeed when we’re dealing with so-called “primitive recursion” this is how things inevitably work: we’re always “systematically counting down” to some defined base case (say f[1] = 1).

When we look at string rewriting (or, for that matter, hypergraph rewriting), evolution that doesn’t terminate is quite ubiquitous. And in direct analogy with, for example, the string rewriting rule ABBB, BBA we can set up the definitions

and then the (infinite) multiway graph begins:

One might think that the possibility of evaluation processes that don’t terminate would be a fundamental problem for a system set up like the Wolfram Language. But it turns out that in current normal usage one basically never runs into the issue except by mistake, when there’s a bug in one’s program.

Still, if one explicitly wants to generate an infinite evaluation structure, it’s not hard to do so. Beyond one can define

and then one gets the multiway graph

which has CatalanNumber[t] (or asymptotically ~4^t) states at layer t.

Another “common bug” form of non-terminating evaluation arises when one makes a primitive-recursion-style definition without giving a “boundary condition”. Here, for example, is the Fibonacci recursion without f[0] and f[1] defined:

And in this case the multiway graph is infinite

with ~2^t states at layer t.

But consider now the “unterminated factorial recursion”

On its own, this just leads to a single infinite chain of evaluation

but if we add the explicit rule that multiplying anything by zero gives zero (i.e. 0 _ → 0) then we get

in which there’s a “zero sink” in addition to an infinite chain of f[–n] evaluations.

Some definitions have the property that they provably always terminate, though it may take a while. An example is the combinator definition we made above:

Here’s the multiway graph starting with f[f[f][f]][f], and terminating in at most 10 steps:

Starting with f[f[f][f][f][f]][f] the multiway graph becomes

but again the evaluation always terminates (and gives a unique result). In this case we can see why this happens: at each step f[x_][y_] effectively “discards ”, thereby “fundamentally getting smaller”, even as it “puffs up” by making three copies of .

But if instead one uses the definition

things get more complicated. In some cases, the multiway evaluation always terminates

while in others, it never terminates:

But then there are cases where there is sometimes termination, and sometimes not:

In this particular case, what’s happening is that evaluation of the first argument of the “top-level f” never terminates, but if the top-level f is evaluated before its arguments then there’s immediate termination. Since the standard Wolfram Language evaluator evaluates arguments first (“leftmost-innermost evaluation”), it therefore won’t terminate in this case—even though there are branches in the multiway evaluation (corresponding to “outermost evaluation”) that do terminate.

Transfinite Evaluation

If a computation reaches a fixed point, we can reasonably say that that’s the “result” of the computation. But what if the computation goes on forever? Might there still be some “symbolic” way to represent what happens—that for example allows one to compare results from different infinite computations?

In the case of ordinary numbers, we know that we can define a “symbolic infinity” ∞ (Infinity in Wolfram Language) that represents an infinite number and has all the obvious basic arithmetic properties:

But what about infinite processes, or, more specifically, infinite multiway graphs? Is there some useful symbolic way to represent such things? Yes, they’re all “infinite”. But somehow we’d like to distinguish between infinite graphs of different forms, say:

And already for integers, it’s been known for more than a century that there’s a more detailed way to characterize infinities than just referring to them all as ∞: it’s to use the idea of transfinite numbers. And in our case we can imagine successively numbering the nodes in a multiway graph, and seeing what the largest number we reach is. For an infinite graph of the form

(obtained say from x = x + 1 or x = {x}) we can label the nodes with successive integers, and we can say that the “largest number reached” is the transfinite ordinal ω.

A graph consisting of two infinite chains is then characterized by 2ω, while an infinite 2D grid is characterized by ω², and an infinite binary tree is characterized by 2^ω.

What about larger numbers? To get to ω^ω we can use a rule like

that effectively yields a multiway graph that corresponds to a tree in which successive layers have progressively larger numbers of branches:

One can think of a definition like x = x + 1 as setting up a “self-referential data structure”, whose specification is finite (in this case essentially a loop), and where the infinite evaluation process arises only when one tries to get an explicit value out of the structure. More elaborate recursive definitions can’t, however, readily be thought of as setting up straightforward self-referential data structures. But they still seem able to be characterized by transfinite numbers.

In general many multiway graphs that differ in detail will be associated with a given transfinite number. But the expectation is that transfinite numbers can potentially provide robust characterizations of infinite evaluation processes, with different constructions of the “same evaluation” able to be identified as being associated with the same canonical transfinite number.

Most likely, definitions purely involving pattern matching won’t be able to generate infinite evaluations beyond ε₀ = ω^ωω...—which is also the limit of where one can reach with proofs based on ordinary induction, Peano Arithmetic, etc. It’s perfectly possible to go further—but one needs to explicitly use functions like NestWhile etc. in the definitions that are given.

And there’s another issue as well: given a particular set of definitions, there’s no limit to how difficult it can be to determine the ultimate multiway graph that’ll be produced. In the end this is a consequence of computational irreducibility, and of the undecidability of the halting problem, etc. And what one can expect in the end is that some infinite evaluation processes one will be able to prove can be characterized by particular transfinite numbers, but others one won’t be able to “tie down” in this way—and in general, as computational irreducibility might suggest, won’t ever allow one to give a “finite symbolic summary”.

The Question of the Observer

One of the key lessons of our Physics Project is the importance of the character of the observer in determining what one “takes away” from a given underlying system. And in setting up the evaluation process—say in the Wolfram Language—the typical objective is to align with the way human observers expect to operate. And so, for example, one normally expects that one will give an expression as input, then in the end get an expression as output. The process of transforming input to output is analogous to the doing of a calculation, the answering of a question, the making of a decision, the forming of a response in human dialog, and potentially the forming of a thought in our minds. In all of these cases, we treat there as being a certain “static” output.

It’s very different from the way physics operates, because in physics “time always goes on”: there’s (essentially) always another step of computation to be done. In our usual description of evaluation, we talk about “reaching a fixed point”. But an alternative would be to say that we reach a state that just repeats unchanged forever—but we as observers equivalence all those repeats, and think of it as having reached a single, unchanging state.

Any modern practical computer also fundamentally works much more like physics: there are always computational operations going on—even though those operations may end up, say, continually putting the exact same pixel in the same place on the screen, so that we can “summarize” what’s going on by saying that we’ve reached a fixed point.

There’s much that can be done with computations that reach fixed points, or, equivalently with functions that return definite values. And in particular it’s straightforward to compose such computations or functions, continually taking output and then feeding it in as input. But there’s a whole world of other possibilities that open up once one can deal with infinite computations. As a practical matter, one can treat such computations “lazily”—representing them as purely symbolic objects from which one can derive particular results if one explicitly asks to do so.

One kind of result might be of the type typical in logic programming or automated theorem proving: given a potentially infinite computation, is it ever possible to reach a specified state (and, if so, what is the path to do so)? Another type of result might involve extracting a particular “time slice” (with some choice of foliation), and in general representing the result as a Multi. And still another type of result (reminiscent of “probabilistic programming”) might involve not giving an explicit Multi, but rather computing certain statistics about it.

And in a sense, each of these different kinds of results can be thought of as what’s extracted by a different kind of observer, who is making different kinds of equivalences.

We have a certain typical experience of the physical world that’s determined by features of us as observers. For example, as we mentioned above, we tend to think of “all of space” progressing “together” through successive moments of time. And the reason we think this is that the regions of space we typically see around us are small enough that the speed of light delivers information on them to us in a time that’s short compared to our “brain processing time”. If we were bigger or faster, then we wouldn’t be able to think of what’s happening in all of space as being “simultaneous” and we’d immediately be thrust into issues of relativity, reference frames, etc.

And in the case of expression evaluation, it’s very much the same kind of thing. If we have an expression laid out in computer memory (or across a network of computers), then there’ll be a certain time to “collect information spatially from across the expression”, and a certain time that can be attributed to each update event. And the essence of array programming (and much of the operation of GPUs) is that one can assume—like in the typical human experience of physical space—that “all of space” is being updated “together”.

But in our analysis above, we haven’t assumed this, and instead we’ve drawn causal graphs that explicitly trace dependencies between events, and show which events can be considered to be spacelike separated, so that they can be treated as “simultaneous”.

We’ve also seen branchlike separation. In the physics case, the assumption is that we as observers sample in an aggregated way across extended regions in branchial space—just as we do across extended regions in physical space. And indeed the expectation is that we encounter what we describe as “quantum effects” precisely because we are of limited extent in branchial space.

In the case of expression evaluation, we’re not used to being extended in branchial space. We typically imagine that we’ll follow some particular evaluation path (say, as defined by the standard Wolfram Language evaluator), and be oblivious to other paths. But, for example, strategies like speculative execution (typically applied at the hardware level) can be thought of as representing extension in branchial space.

And at a theoretical level, one certainly thinks of different kinds of “observations” in branchial space. In particular, there’s nondeterministic computation, in which one tries to identify a particular “thread of history” that reaches a given state, or a state with some property one wants.

One crucial feature of observers like us is that we are computationally bounded—which puts limitations on the kinds of observations we can make. And for example computational irreducibility then limits what we can immediately know (and aggregate) about the evolution of systems through time. And similarly multicomputational irreducibility limits what we can immediately know (and aggregate) about how systems behave across branchial space. And insofar as any computational devices we build in practice must be ones that we as observers can deal with, it’s inevitable that they’ll be subject to these kinds of limitations. (And, yes, in talking about quantum computers there tends to be an implicit assumption that we can in effect overcome multicomputational irreducibility, and “knit together” all the different computational paths of history—but it seems implausible that observers like us can actually do this, or can in general derive definite results without expending computationally irreducible effort.)

One further small comment about observers concerns what in physics are called closed timelike curves—essentially loops in time. Consider the definition:

This gives for example the multiway graph:

One can think of this as connecting the future to the past—something that’s sometimes interpreted as “allowing time travel”. But really this is just a more (time-)distributed version of a fixed point. In a fixed point, a single state is constantly repeated. Here a sequence of states (just two in the example given here) get visited repeatedly. The observer could treat these states as continually repeating in a cycle, or could coarse grain and conclude that “nothing perceptible is changing”.

In spacetime we think of observers as making particular choices of simultaneity surfaces—or in effect picking particular ways to “parse” the causal graph of events. In branchtime the analog of this is that observers pick how to parse the multiway graph. Or, put another way, observers get to choose a path through the multiway graph, corresponding to a particular evaluation order or evaluation scheme. In general, there is a tradeoff between the choices made by the observer, and the behavior generated by applying the rules of the system.

But if the observer is computationally bounded, they cannot overcome the computational irreducibility—or multicomputational irreducibility—of the behavior of the system. And as a result, if there is complexity in the detailed behavior of the system, the observer will not be able to avoid it at a detailed level by the choices they make. Though a critical idea of our Physics Project is that by appropriate aggregation, the observer will detect certain aggregate features of the system, that have robust characteristics independent of the underlying details. In physics, this represents a bulk theory suitable for the perception of the universe by observers like us. And presumably there is an analog of this in expression evaluation. But insofar as we’re only looking at the evaluation of expressions we’ve engineered for particular computational purposes, we’re not yet used to seeing “generic bulk expression evaluation”.

But this is exactly what we’ll see if we just go out and run “arbitrary programs”, say found by enumerating certain classes of programs (like combinators or multiway Turing machines). And for observers like us these will inevitably “seem very much like physics”.

The Tree Structure of Expressions

Although we haven’t talked about this so far, any expression fundamentally has a tree structure. So, for example, (1 + (2 + 2)) + (3 + 4) is represented—say internally in the Wolfram Language—as the tree:

So how does this tree structure interact with the process of evaluation? In practice it means for example that in the standard Wolfram Language evaluator there are two different kinds of recursion going on. The first is the progressive (“timelike”) reevaluation of subexpressions that change during evaluation. And the second is the (“spacelike” or “treelike”) scanning of the tree.

In what we’ve discussed above, we’ve focused on evaluation events and their relationships, and in doing so we’ve concentrated on the first kind of recursion—and indeed we’ve often elided some of the effects of the second kind by, for example, immediately showing the result of evaluating Plus[2, 2] without showing more details of how this happens.

But here now is a more complete representation of what’s going on in evaluating this simple expression:

The solid gray lines in this “trace graph” indicate the subparts of the expression tree at each step. The dashed gray lines indicate how these subparts are combined to make expressions. And the red lines indicate actual evaluation events where rules (either built in or specified by definitions) are applied to expressions.

It’s possible to read off things like causal dependence between events from the trace graph. But there’s a lot else going on. Much of it is at some level irrelevant—because it involves recursing into parts of the expression tree (like the head Plus) where no evaluation events occur. Removing these parts we then get an elided trace graph in which for example the causal dependence is clearer:

Here’s the trace graph for the evaluation of f[5] with the standard recursive Fibonacci definition

and here’s its elided form:

At least when we discussed single-way evaluation above, we mostly talked about timelike and spacelike relations between events. But with tree-structured expressions there are also treelike relations.

Consider the rather trivial definition

and look at the multiway graph for the evaluation of f[f[0]]:

What is the relation between the event on the left branch, and the top event on the right branch? We can think of them as being treelike separated. The event on the left branch transforms the whole expression tree. But the event on the right branch just transforms a subexpression.

Spacelike-separated events affect disjoint parts in an expression (i.e. ones on distinct branches of the expression tree). But treelike-separated events affect nested parts of an expression (i.e. ones that appear on a single branch in the expression tree). Inevitably, treelike-separated events also have a kind of one-way branchlike separation: if the “higher event” in the tree happens, the “lower one” cannot.

In terms of Wolfram Language part numbers, spacelike-separated events affect parts with disjoint numbers, say {2, 5} and {2, 8}. But treelike-separated events affect parts with overlapping sequences of part numbers, say {2} and {2, 5} or {2, 5} and {2, 5, 1}.

In our Physics Project there’s nothing quite like treelike relations built in. The “atoms of space” are related by a hypergraph—without any kind of explicit hierarchical structure. The hypergraph can take on what amounts to a hierarchical structure, but the fundamental transformation rules won’t intrinsically take account of this.

The hierarchical structure of expressions is incredibly important in their practical use—where it presumably leverages the hierarchical structure of human language, and of ways we talk about the world:

We’ll see soon below that we can in principle represent expressions without having hierarchical structure explicitly built in. But in almost all uses of expressions—say in Wolfram Language—we end up needing to have hierarchical structure.

If we were only doing single-way evaluation the hierarchical structure of expressions would be important in determining the order of evaluation to be used, but it wouldn’t immediately enmesh with core features of the evaluation process. But in multiway evaluation “higher” treelike-separated events can in effect cut off the evaluation histories of “lower” ones—and so it’s inevitably central to the evaluation process. For spacelike- and branchlike-separated events, we can always choose different reference frames (or different spacelike or branchlike surfaces) that arrange the events differently. But treelike-separated events—a little like timelike-separated ones—have a certain forced relationship that cannot be affected by an observer’s choices.

Grinding Everything Down to Hypergraphs

To draw causal graphs—and in fact to do a lot of what we’ve done here—we need to know “what depends on what”. And with our normal setup for expressions this can be quite subtle and complicated. We apply the rule to to give the result . But does the a that “comes out” depend on the a that went in, or is it somehow something that’s “independently generated”? Or, more extremely, in a transformation like , to what extent is it “the same 1” that goes in and comes out? And how do these issues of dependence work when there are the kinds of treelike relations discussed in the previous section?

The Wolfram Language evaluator defines how expressions should be evaluated—but doesn’t immediately specify anything about dependencies. Often we can look “after the fact” and deduce what “was involved” and what was not—and thus what should be considered to depend on what. But it’s not uncommon for it to be hard to know what to say—forcing one to make what seem likely arbitrary decisions. So is there any way to avoid this, and to set things up so that dependency becomes somehow “obvious”?

It turns out that there is—though, perhaps not surprisingly, it comes with difficulties of its own. But the basic idea is to go “below expressions”, and to “grind everything down” to hypergraphs whose nodes are ultimate direct “carriers” of identity and dependency. It’s all deeply reminiscent of our Physics Project—and its generalization in the ruliad. Though in those cases the individual elements (or “emes” as we call them) exist far below the level of human perception, while in the hypergraphs we construct for expressions, things like symbols and numbers appear directly as emes.

So how can we “compile” arbitrary expressions to hypergraphs? In the Wolfram Language something like a + b + c is the “full-form” expression

which corresponds to the tree:

And the point is that we can represent this tree by a hypergraph:

Plus, a, b and c appear directly as “content nodes” in the hypergraph. But there are also “infrastructure nodes” (here labeled with integers) that specify how the different pieces of content are “related”—here with a 5-fold hyperedge representing Plus with three arguments. We can write this hypergraph out in “symbolic form” as:

Let’s say instead we have the expression or Plus[a, Plus[b, c]], which corresponds to the tree:

We can represent this expression by the hypergraph

which can be rendered visually as:

What does evaluation do to such hypergraphs? Essentially it must transform collections of hyperedges into other collections of hyperedges. So, for example, when x_ + y_ is evaluated, it transforms a set of 3 hyperedges to a single hyperedge according to the rule:

(Here the list on the left-hand side represents three hyperedges in any order—and so is effectively assumed to be orderless.) In this rule, the literal Plus acts as a kind of key to determine what should happen, while the specific patterns define how the input and output expressions should be “knitted together”.

So now let’s apply this rule to the expression 10 + (20 + 30). The expression corresponds to the hypergraph

where, yes, there are integers both as content elements, and as labels or IDs for “infrastructure nodes”. The rule operates on collections of hyperedges, always consuming 3 hyperedges, and generating 1. We can think of the hyperedges as “fundamental tokens”. And now we can draw a token-event graph to represent the evaluation process:

Here’s the slightly more complicated case of (10 + (20 + 20)) + (30 + 40):

But here now is the critical point. By looking at whether there are emes in common from one event to another, we can determine whether there is dependency between those events. Emes are in a sense “atoms of existence” that maintain a definite identity, and immediately allow one to trace dependency.

So now we can fill in causal edges, with each edge labeled by the emes it “carries”:

Dropping the hyperedges, and adding in an initial “Big Bang” event, we get the (multiway) causal graph:

We should note that in the token-event graph, each expression has been “shattered” into its constituent hyperedges. Assembling the tokens into recognizable expressions effectively involves setting up a particular foliation of the token-event graph. But if we do this, we get a multiway graph expressed in terms of hypergraphs

or in visual form:

As a slightly more complicated case, consider the recursive computation of the Fibonacci number f[2]. Here is the token-event graph in this case:

And here is the corresponding multiway causal graph, labeled with the emes that “carry causality”:

Every kind of expression can be “ground down” in some way to hypergraphs. For strings, for example, it’s convenient to make a separate token out of every character, so that “ABBAAA” can be represented as:

It’s interesting to note that our hypergraph setup can have a certain similarity to machine-level representations of expressions, with every eme in effect corresponding to a pointer to a certain memory location. Thus, for example, in the representation of the string, the infrastructure emes define the pointer structure for a linked list—with the content emes being the “payloads” (and pointing to globally shared locations, like ones for A and B).

Transformations obtained by applying rules can then be thought of as corresponding just to rearranging pointers. Sometimes “new emes” have to be created, corresponding to new memory being allocated. We don’t have an explicit way to “free” memory. But sometimes some part of the hypergraph will become disconnected—and one can then imagine disconnected pieces to which the observer is not attached being garbage collected.

The Rulial Case

So far we’ve discussed what happens in the evaluation of particular expressions according to particular rules (where those rules could just be all the ones that are built into Wolfram Language). But the concept of the ruliad suggests thinking about all possible computations—or, in our terms here, all possible evaluations. Instead of particular expressions, we are led to think about evaluating all possible expressions. And we are also led to think about using all possible rules for these evaluations.

As one simple approach to this, instead of looking, for example, at a single combinator definition such as

used to evaluate a single expression such as

we can start enumerating all possible combinator rules

and apply them to evaluate all possible expressions:

Various new phenomena show up here. For example, there is now immediately the possibility of not just spacelike and branchlike separation, but also what we can call rulelike separation.

In a trivial case, we could have rules like

and then evaluating x will lead to two events which we can consider rulelike separated:

In the standard Wolfram Language system, the definitions and x = b would overwrite each other. But if we consider rulial multiway evaluation, we’d have branches for each of these definitions.

In what we’ve discussed before, we effectively allow evaluation to take infinite time, as well as infinite space and infinite branchial space. But now we’ve got the new concept of infinite rulial space. We might say from the outset that, for example, we’re going to use all possible rules. Or we might have what amounts to a dynamical process that generates possible rules.

And the key point is that as soon as that process is in effect computation universal, there is a way to translate from one instance of it to another. Different specific choices will lead to a different basis—but in the end they’ll all eventually generate the full ruliad.

And actually, this is where the whole concept of expression evaluation ultimately merges with fundamental physics. Because in both cases, the limit of what we’re doing will be exactly the same: the full ruliad.

The Practical Computing Story

The formalism we’ve discussed here—and particularly its correspondence with fundamental physics—is in many ways a new story. But it has precursors that go back more than a century. And indeed as soon as industrial processes—and production lines—began to be formalized, it became important to understand interdependencies between different parts of a process. By the 1920s flowcharts had been invented, and when digital computers were developed in the 1940s they began to be used to represent the “flow” of programs (and in fact Babbage had used something similar even in the 1840s). At first, at least as far as programming was concerned, it was all about the “flow of control”—and the sequence in which things should be done. But by the 1970s the notion of the “flow of data” was also widespread—in some ways reflecting back to actual flow of electrical signals. In some simple cases various forms of “visual programming”—typically based on connecting virtual wires—have been popular. And even in modern times, it’s not uncommon to talk about “computation graphs” as a way to specify how data should be routed in a computation, for example in sequences of operations on tensors (say for neural net applications).

A different tradition—originating in mathematics in the late 1800s—involved the routine use of “abstract functions” like f(x). Such abstract functions could be used both “symbolically” to represent things, and explicitly to “compute” things. All sorts of (often ornate) formalism was developed in mathematical logic, with combinators arriving in 1920, and lambda calculus in 1935. By the late 1950s there was LISP, and by the 1970s there was a definite tradition of “functional programming” involving the processing of things by successive application of different functions.

The question of what really depended on what became more significant whenever there was the possibility of doing computations in parallel. This was already being discussed in the 1960s, but became more popular in the early 1980s, and in a sense finally “went mainstream” with GPUs in the 2010s. And indeed our discussion of causal graphs and spacelike separation isn’t far away from the kind of thing that’s often discussed in the context of designing parallel algorithms and hardware. But one difference is that in those cases one’s usually imagining having a “static” flow of data and control, whereas here we’re routinely considering causal graphs, etc. that are being created “on the fly” by the actual progress of a computation.

In many situations—with both algorithms and hardware—one has precise control over when different “events” will occur. But in distributed systems it’s also common for events to be asynchronous. And in such cases, it’s possible to have “conflicts”, “race conditions”, etc. that correspond to branchlike separation. There have been various attempts—many originating in the 1970s—to develop formal “process calculi” to describe such systems. And in some ways what we’re doing here can be seen as a physics-inspired way to clarify and extend these kinds of approaches.

The concept of multiway systems also has a long history—notably appearing in the early 1900s in connection with game graphs, formal group theory and various problems in combinatorics. Later, multiway systems would implicitly show up in considerations of automated theorem proving and nondeterministic computation. In practical microprocessors it’s been common for a decade or so to do “speculative execution” where multiple branches in code are preemptively followed, keeping only the one that’s relevant given actual input received.

And when it comes to branchlike separation, a notable practical example arises in version control and collaborative editing systems. If a piece of text has changes at two separated places (“spacelike separation”), then these changes (“diffs”) can be applied in any order. But if these changes involve the same content (e.g. same characters) then there can be a conflict (“merge conflict”) if one tries to apply the changes—in effect reflecting the fact that these changes were made by branchlike-separated “change events” (and to trace them requires creating different “forks” or what we might call different histories).

It’s perhaps worth mentioning that as soon as one has the concept of an “expression” one is led to the concept of “evaluation”—and as we’ve seen many times here, that’s even true for arithmetic expressions, like 1 + (2 + 3). We’ve been particularly concerned with questions about “what depends on what” in the process of evaluation. But in practice there’s often also the question of when evaluation happens. The Wolfram Language, for example, distinguishes between “immediate evaluation” done when a definition is made, and “delayed evaluation” done when it’s used. There’s also lazy evaluation where what’s immediately generated is a symbolic representation of the computation to be done—with steps or pieces being explicitly computed only later, when they are requested.

But what really is “evaluation”? If our “input expression” is 1 + 1, we typically think of this as “defining a computation that can be done”. Then the idea of the “process of evaluation” is that it does that computation, deriving a final “value”, here 2. And one view of the Wolfram Language is that its whole goal is to set up a collection of transformations that do as many computations that we know how to do as possible. Some of those transformations effectively incorporate “factual knowledge” (like knowledge of mathematics, or chemistry, or geography). But some are more abstract, like transformations defining how to do transformations, say on patterns.

These abstract transformations are in a sense the easiest to trace—and often above that’s what we’ve concentrated on. But usually we’ve allowed ourselves to do at least some transformations—like adding numbers—that are built into the “insides” of the Wolfram Language. It’s perhaps worth mentioning that in conveniently representing such a broad range of computational processes the Wolfram Language ends up having some quite elaborate evaluation mechanisms. A common example is the idea of functions that “hold their arguments”, evaluating them only as “specifically requested” by the innards of the function. Another—that in effect creates a “side chain” to causal graphs—are conditions (e.g. associated with /;) that need to be evaluated to determine whether patterns are supposed to match.

Evaluation is in a sense the central operation in the Wolfram Language. And what we’ve seen here is that it has a deep correspondence with what we can view as the “central operation” of physics: the passage of time. Thinking in terms of physics helps organize our thinking about the process of evaluation—and it also suggests some important generalizations, like multiway evaluation. And one of the challenges for the future is to see how to take such generalizations and “package” them as part of our computational language in a form that we humans can readily understand and make use of.

Some Personal History: Recursion Control in SMP

It was in late 1979 that I first started to design my SMP (“Symbolic Manipulation Program”) system. I’d studied both practical computer systems and ideas from mathematical logic. And one of my conclusions was that any definition you made should always get used, whenever it could. If you set , then you set , you should get (not ) if you asked for . It’s what most people would expect should happen. But like almost all fundamental design decisions, in addition to its many benefits, it had some unexpected consequences. For example, it meant that if you set without having given a value for , you’d in principle get an infinite loop.

Back in 1980 there were computer scientists who asserted that this meant the “infinite evaluation” I’d built into the core of SMP “could never work”. Four decades of experience tells us rather definitively that in practice they were wrong about this (essentially because people just don’t end up “falling into the pothole” when they’re doing actual computations they want to do). But questions like those about made me particularly aware of issues around recursive evaluation. And it bothered me that a recursive factorial definition like f[n_]:=n f[n–1] (the rather less elegant SMP notation was f[$n]::$n f[$1-1]) might just run infinitely if it didn’t have a base case (f[1] = 1), rather than terminating with the value 0, which it “obviously should have”, given that at some point one’s computing 0×….

So in SMP I invented a rather elaborate scheme for recursion control that “solved” this problem. And here’s what happens in SMP (now running on a reconstructed virtual machine):

And, yes, if one includes the usual base case for factorial, one gets the usual answer:

So what is going on here? Section 3.1 of the SMP documentation in principle tells the story. In SMP I used the term “simplification” for what I’d now call “evaluation”, both because I imagined that most transformations one wanted would make things “simpler” (as in ), and because there was a nice pun between the name SMP and the function Smp that carried out the core operation of the system (yes, SMP rather foolishly used short names for built-in functions). Also, it’s useful to know that in SMP I called an ordinary expression like f[x, y, …] a “projection”: its “head” f was called its “projector”, and its arguments x, y, … were called “filters”.

As the Version 1.0 documentation from July 1981 tells it, “simplification” proceeds like this:

By the next year, it was a bit more sophisticated, though the default behavior didn’t change:

With the definitions above, the value of f itself was (compare Association in Wolfram Language):

But the key to evaluation without the base case actually came in the “properties” of multiplication:

In SMP True was (foolishly) 1. It’s notable here that Flat corresponds to the attribute Flat in Wolfram Language, Comm to Orderless and Ldist to Listable. (Sys indicated that this was a built-in system function, while Tier dealt with weird consequences of the attempted unification of arrays and functions into an association-like construct.) But the critical property here was Smp. By default its value was Inf (for Infinity). But for Mult (Times) it was 1.

And what this did was to tell the SMP evaluator that inside any multiplication, it should allow a function (like f) to be called recursively at most once before the actual multiplication was done. Telling SMP to trace the evaluation of f[5] we then see:

So what’s going on here? The first time f appears inside a multiplication its definition is used. But when f appears recursively a second time, it’s effectively frozen—and the multiplication is done using its frozen form, with the result that as soon as a 0 appears, one just ends up with 0.

Reset the Smp property of Mult to infinity, and the evaluation runs away, eventually producing a rather indecorous crash:

In effect, the Smp property defines how many recursive evaluations of arguments should be done before a function itself is evaluated. Setting the Smp property to 0 has essentially the same effect as the HoldAll attribute in Wolfram Language: it prevents arguments from being evaluated until a function as a whole is evaluated. Setting Smp to value k basically tells SMP to do only k levels of “depth-first” evaluation before collecting everything together to do a “breadth-first evaluation”.

Let’s look at this for a recursive definition of Fibonacci numbers:

With the Smp property of Plus set to infinity, the sequence of evaluations of f follows a pure “depth-first” pattern

where we can plot the sequence of f[n] evaluated as:

But with the default setting of 1 for the Smp property of Plus the sequence is different

and now the sequence of f[n] evaluated is:

In the pure depth-first case all the exponentially many leaves of the Fibonacci tree are explicitly evaluated. But now the evaluation of f[n] is being frozen after each step and terms are being collected and combined. Starting for example from f[10] we get f[9] + f[8]. And evaluating another step we get f[8] + f[7] + f[7] + f[6]. But now the f[7]’s can be combined into f[8] + 2f[7] + f[6] so that they don’t both have to separately be evaluated. And in the end only quadratically many separate evaluations are needed to get the final result.

I don’t now remember quite why I put it in, but SMP also had another piece of recursion control: the Rec property of a symbol—which basically meant “it’s OK for this symbol to appear recursively; don’t count it when you’re trying to work out whether to freeze an evaluation”.

And it’s worth mentioning that SMP also had a way to handle the original issue:

It wasn’t a terribly general mechanism, but at least it worked in this case:

I always thought that SMP’s “wait and combine terms before recursing” behavior was quite clever, but beyond the factorial and Fibonacci examples here I’m not sure I ever found clear uses for it. Still, with our current physics-inspired way of looking at things, we can see that this behavior basically corresponded to picking a “more spacetime-like” foliation of the evaluation graph.

And it’s a piece of personal irony that right around the time I was trying to figure out recursive evaluation in SMP, I was also working on gauge theories in physics—which in the end involve very much the same kinds of issues. But it took another four decades—and the development of our Physics Project—before I saw the fundamental connection between these things.

After SMP: Further Personal History

The idea of parallel computation was one that I was already thinking about at the very beginning of the 1980s—partly at a theoretical level for things like neural nets and cellular automata, and partly at a practical level for SMP (and indeed by 1982 I had described a Ser property in SMP that was supposed to ensure that the arguments of a particular function would always get evaluated in a definite order “in series”). Then in 1984 I was involved in trying to design a general language for parallel computation on the Connection Machine “massively parallel” computer. The “obvious” approach was just to assume that programs would be set up to operate in steps, even if at each step many different operations might happen in parallel. But I somehow thought that there must be a better approach, somehow based on graphs, and graph rewriting. But back then I didn’t, for example, think of formulating things in terms of causal graphs. And while I knew about phenomena like race conditions, I hadn’t yet internalized the idea of constructing multiway graphs to “represent all possibilities”.

When I started designing Mathematica—and what’s now the Wolfram Language—in 1986, I used the same core idea of transformation rules for symbolic expressions that was the basis for SMP. But I was able to greatly streamline the way expressions and their evaluation worked. And not knowing compelling use cases, I decided not to set up the kind of elaborate recursion control that was in SMP, and instead just to concentrate on basically two cases: functions with ordinary (essentially leftmost-innermost) evaluation and functions with held-argument (essentially outermost) evaluation. And I have to say that in three decades of usages and practical applications I haven’t really missed having more elaborate recursion controls.

In working on A New Kind of Science in the 1990s, issues of evaluation order first came up in connection with “symbolic systems” (essentially, generalized combinators). They then came up more poignantly when I explored the possible computational “infrastructure” for spacetime—and indeed that was where I first started explicitly discussing and constructing causal graphs.

But it was not until 2019 and early 2020, with the development of our Physics Project, that clear concepts of spacelike and branchlike separation for events emerged. The correspondence with expression evaluation got clearer in December 2020 when—in connection with the centenary of their invention—I did an extensive investigation of combinators (leading to my book Combinators). And as I started to explore the general concept of multicomputation, and its many potential applications, I soon saw the need for systematic ways to think about multicomputational evaluation in the context of symbolic language and symbolic expressions.

In both SMP and Wolfram Language the main idea is to “get results”. But particularly for debugging it’s always been of interest to see some kind of trace of how the results are obtained. In SMP—as we saw above—there was a Trace property that would cause any evaluation associated with a particular symbol to be printed. But what about an actual computable representation of the “trace”? In 1990 we introduced the function Trace in the Wolfram Language—which produces what amounts to a symbolic representation of an evaluation process.

I had high hopes for Trace—and for its ability to turn things like control flows into structures amenable to direct manipulation. But somehow what Trace produces is almost always too difficult to understand in real cases. And for many years I kept the problem of “making a better Trace” on my to-do list, though without much progress.

The problem of “exposing a process of computation” is quite like the problem of presenting a proof. And in 2000 I had occasion to use automated theorem proving to produce a long proof of my minimal axiom system for Boolean algebra. We wanted to introduce such methods into Mathematica (or what’s now the Wolfram Language). But we were stuck on the question of how to represent proofs—and in 2007 we ended up integrating just the “answer” part of the methods into the function FullSimplify.

By the 2010s we’d had the experience of producing step-by-step explanations in Wolfram|Alpha, as well as exploring proofs in the context of representing pure-mathematical knowledge. And finally in 2018 we introduced FindEquationalProof, which provided a symbolic representation of proofs—at least ones based on successive pattern matching and substitution—as well as a graphical representation of the relationships between lemmas.

After the arrival of our Physics Project—as well as my exploration of combinators—I returned to questions about the foundations of mathematics and developed a whole “physicalization of metamathematics” based on tracing what amount to multiway networks of proofs. But the steps in these proofs were still in a sense purely structural, involving only pattern matching and substitution.

I explored other applications of “multicomputation”, generating multiway systems based on numbers, multiway systems representing games, and so on. And I kept on wondering—and sometimes doing livestreamed discussions about—how best to create a language design around multicomputation. And as a first step towards that, we developed the TraceGraph function in the Wolfram Function Repository, which finally provided a somewhat readable graphical rendering of the output of Trace—and began to show the causal dependencies in at least single-way computation. But what about the multiway case? For the Physics Project we’d already developed MultiwaySystem and related functions in the Wolfram Function Repository. So now the question was: how could one streamline this and have it provide essentially a multiway generalization of TraceGraph? We began to think about—and implement—concepts like Multi, and imagine ways in which general multicomputation could encompass things like logic programming and probabilistic programming, as well as nondeterministic and quantum computation.

But meanwhile, the “ question” that had launched my whole adventure in recursion control in SMP was still showing up—43 years later—in the Wolfram Language. It had been there since Version 1.0, though it never seemed to matter much, and we’d always handled it just by having a global “recursion limit”—and then “holding” all further subevaluations:

But over the years there’d been increasing evidence that this wasn’t quite adequate, and that for example further processing of the held form (even, for example, formatting it) could in extreme cases end up triggering even infinite cascades of evaluations. So finally—in Version 13.2 at the end of last year—we introduced the beginnings of a new mechanism to cut off “runaway” computations, based on a construct called TerminatedEvaluation:

And from the beginning we wanted to see how to encode within TerminatedEvaluation information about just what evaluation had been terminated. But to do this once again seemed to require having a way to represent the “ongoing process of evaluation”—leading us back to Trace, and making us think about evaluation graphs, causal graphs, etc.

At the beginning x = x + 1 might just have seemed like an irrelevant corner case—and for practical purposes it basically is. But already four decades ago it led me to start thinking not just about the results of computations, but also how their internal processes can be systematically organized. For years, I didn’t really connect this to my work on explicit computational processes like those in systems such as cellular automata. Hints of such connections did start to emerge as I began to try to build computational models of fundamental physics. But looking back I realize that in x = x + 1 there was already in a sense a shadow of what was to come in our Physics Project and in the whole construction of the ruliad.

Because x = x + 1 is something which—like physics and like the ruliad—necessarily generates an ongoing process of computation. One might have thought that the fact that it doesn’t just “give an answer” was in a sense a sign of uselessness. But what we’ve now realized is that our whole existence and experience is based precisely on “living inside a computational process” (which, fortunately for us, hasn’t just “ended with an answer”). Expression evaluation is in its origins intended as a “human-accessible” form of computation. But what we’re now seeing is that its essence also inevitably encompasses computations that are at the core of fundamental physics. And by seeing the correspondence between what might at first appear to be utterly unrelated intellectual directions, we can expect to inform both of them. Which is what I have started to try to do here.

Notes & Thanks

What I’ve described here builds quite directly on some of my recent work, particularly as covered in my books Combinators: A Centennial View and Metamathematics: Physicalization & Foundations. But as I mentioned above, I started thinking about related issues at the beginning of the 1980s in connection with the design of SMP, and I’d like to thank members of the SMP development team for discussions at that time, particularly Chris Cole, Jeff Greif and Tim Shaw. Thanks also to Bruce Smith for his 1990 work on Trace in Wolfram Language, and for encouraging me to think about symbolic representations of computational processes. In much more recent times, I’d particularly like to thank Jonathan Gorard for his extensive conceptual and practical work on multiway systems and their formalism, both in our Physics Project and beyond. Some of the directions described here have (at least indirectly) been discussed in a number of recent Wolfram Language design review livestreams, with particular participation by Ian Ford, Nik Murzin, and Christopher Wolfram, as well as Dan Lichtblau and Itai Seggev. Thanks also to Wolfram Institute fellows Richard Assar and especially Nik Murzin for their help with this piece.

AIs and Alien Minds

How do alien minds perceive the world? It’s an old and oft-debated question in philosophy. And it now turns out to also be a question that rises to prominence in connection with the concept of the ruliad that’s emerged from our Wolfram Physics Project.

I’ve wondered about alien minds for a long time—and tried all sorts of ways to imagine what it might be like to see things from their point of view. But in the past I’ve never really had a way to build my intuition about it. That is, until now. So, what’s changed? It’s AI. Because in AI we finally have an accessible form of alien mind.

We typically go to a lot of trouble to train our AIs to produce results that are like we humans would do. But what if we take a human-aligned AI, and modify it? Well, then we get something that’s in effect an alien AI—an AI aligned not with us humans, but with an alien mind.

So how can we see what such an alien AI—or alien mind—is “thinking”? A convenient way is to try to capture its “mental imagery”: the image it forms in its “mind’s eye”. Let’s say we use a typical generative AI to go from a description in human language—like “a cat in a party hat”—to a generated image:

It’s exactly the kind of image we’d expect—which isn’t surprising, because it comes from a generative AI that’s trained to “do as we would”. But now let’s imagine taking the neural net that implements this generative AI, and modifying its insides—say by resetting weights that appear in its neural net.

By doing this we’re in effect going from a human-aligned neural net to some kind of “alien” one. But this “alien” neural net will still produce some kind of image—because that’s what a neural net like this does. But what will the image be? Well, in effect, it’s showing us the mental imagery of the “alien mind” associated with the modified neural net.

But what does it actually look like? Well, here’s a sequence obtained by progressively modifying the neural net—in effect making it “progressively more alien”:

At the beginning it’s still a very recognizable picture of “a cat in a party hat”. But it soon becomes more and more alien: the mental image in effect diverges further from the human one—until it no longer “looks like a cat”, and in the end looks, at least to us, rather random.

There are many details of how this works that we’ll be discussing below. But what’s important is that—by studying the effects of changing the neural net—we now have a systematic “experimental” platform for probing at least one kind of “alien mind”. We can think of what we’re doing as a kind of “artificial neuroscience”, probing not actual human brains, but neural net analogs of them.

And we’ll see many parallels to neuroscience experiments. For example, we’ll often be “knocking out” particular parts of our “neural net brain”, a little like how injuries such as strokes can knock out parts of a human brain. But we know that when a human brain suffers a stroke, this can lead to phenomena like “hemispatial neglect”, in which a stroke victim asked to draw a clock will end up drawing just one side of the clock—a little like the pictures of cats “degrade” when parts of the “neural net brain” are knocked out.

Of course, there are many differences between real brains and artificial neural nets. But most of the core phenomena we’ll observe here seem robust and fundamental enough that we can expect them to span very different kinds of “brains”—human, artificial and alien. And the result is that we can begin to build up intuition about what the worlds of different—and alien—minds can be like.

Generating Images with AIs

How does an AI manage to create a picture, say of a cat in a party hat? Well, the AI has to be trained on “what makes a reasonable picture”—and how to determine what a picture is of. Then in some sense what the AI does is to start generating “reasonable” pictures at random, in effect continually checking what the picture it’s generating seems to be “of”, and tweaking it to guide it towards being a picture of what one wants.

So what counts as a “reasonable picture”? If one looks at billions of pictures—say on the web—there are lots of regularities. For example, the pixels aren’t random; nearby ones are usually highly correlated. If there’s a face, it’s usually more or less symmetrical. It’s more common to have blue at the top of a picture, and green at the bottom. And so on. And the important technological point is that it turns out to be possible to use a neural network to capture regularities in images, and to generate random images that exhibit them.

Here are some examples of “random images” generated in this way:

And the idea is that these images—while each is “random” in its specifics—will in general follow the “statistics” of the billions of images from the web on which the neural network has been “trained”. We’ll be talking more about images like these later. But for now suffice it to say that while some may just look like abstract patterns, others seem to contain things like landscapes, human forms, etc. And what’s notable is that none just look like “random arrays of pixels”; they all show some kind of “structure”. And, yes, given that they’ve been trained from pictures on the web, it’s not too surprising that the “structure” sometimes includes things like human forms.

But, OK, let’s say we specifically want a picture of a cat in a party hat. From all of the almost infinitely large number of possible “well-structured” random images we might generate, how do we get one that’s of a cat in a party hat? Well, a first question is: how would we know if we’ve succeeded? As humans, we could just look and see what our image is of. But it turns out we can also train a neural net to do this (and, no, it doesn’t always get it exactly right):

How is the neural net trained? The basic idea is to take billions of images—say from the web—for which corresponding captions have been provided. Then one progressively tweaks the parameters of the neural net to make it reproduce these captions when it’s fed the corresponding images. But the critical point is the neural net turns out to do more: it also successfully produces “reasonable” captions for images it’s never seen before. What does “reasonable” mean? Operationally, it means captions that are similar to what we humans might assign. And, yes, it’s far from obvious that a computationally constructed neural net will behave at all like us humans, and the fact that it does is presumably telling us fundamental things about how human brains work.

But for now what’s important is that we can use this captioning capability to progressively guide images we produce towards what we want. Start from “pure randomness”. Then try to “structure the randomness” to make a “reasonable” picture, but at every step see in effect “what the caption would be”. And try to “go in a direction” that “leads towards” a picture with the caption we want. Or, in other words, progressively try to get to a picture that’s of what we want.

The way this is set up in practice, one starts from an array of random pixels, then iteratively forms the picture one wants:

Different initial arrays lead to different final pictures—though if everything works correctly, the final pictures will all be of “what one asked for”, in this case a cat in a party hat (and, yes, there are a few “glitches”):

We don’t know how mental images are formed in human brains. But it seems conceivable that the process is not too different. And that in effect as we’re trying to “conjure up a reasonable image”, we’re continually checking if it’s aligned with what we want—so that, for example, if our checking process is impaired we can end up with a different image, as in hemispatial neglect.

The Notion of Interconcept Space

That everything can ultimately be represented in terms of digital data is foundational to the whole computational paradigm. But the effectiveness of neural nets relies on the slightly different idea that it’s useful to treat at least many kinds of things as being characterized by arrays of real numbers. In the end one might extract from a neural net that’s giving captions to images the word “cat”. But inside the neural net it’ll operate with arrays of numbers that correspond in some fairly abstract way to the image you’ve given, and the textual caption it’ll finally produce.

And in general neural nets can typically be thought of as associating “feature vectors” with things—whether those things are images, text, or anything else. But whereas words like “cat” and “dog” are discrete, the feature vectors associated with them just contain collections of real numbers. And this means that we can think of a whole space of possibilities, with “cat” and “dog” just corresponding to two specific points.

So what’s out there in that space of possibilities? For the feature vectors we typically deal with in practice the space is many-thousand-dimensional. But we can for example look at the (nominally straight) line from the “dog point” to the “cat point” in this space, and even generate sample images of what comes between:

And, yes, if we want to, we can keep going “beyond cat”—and pretty soon things start becoming quite weird:

We can also do things like look at the line from a plane to a cat—and, yes, there’s strange stuff in there (wings hat ears?):

What about elsewhere? For example, what happens “around” our standard “cat in a party hat”? With the particular setup we’re using, there’s a 2304-dimensional space of possibilities. But as an example, we look at what we get on a particular 2D plane through the “standard cat” point:

Our “standard cat” is in the middle. But as we move away from the “standard cat” point, progressively weirder things happen. For a while there are recognizable (if perhaps demonic) cats to be seen. But soon there isn’t much “catness” in evidence—though sometimes hats do remain (in what we might characterize as an “all hat, no cat” situation, reminiscent of the Texan “all hat, no cattle”).

How about if we pick other planes through the standard cat point? All sorts of images appear:

But the fundamental story is always the same: there’s a kind of “cat island”, beyond which there are weird and only vaguely cat-related images—encircled by an “ocean” of what seem like purely abstract patterns with no obvious cat connection. And in general the picture that emerges is that in the immense space of possible “statistically reasonable” images, there are islands dotted around that correspond to “linguistically describable concepts”—like cats in party hats.

The islands normally seem to be roughly “spherical”, in the sense that they extend about the same nominal distance in every direction. But relative to the whole space, each island is absolutely tiny—something like perhaps a fraction 2^–2000 ≈ 10^–600 of the volume of the whole space. And between these islands there lie huge expanses of what we might call “interconcept space”.

What’s out there in interconcept space? It’s full of images that are “statistically reasonable” based on the images we humans have put on the web, etc.—but aren’t of things we humans have come up with words for. It’s as if in developing our civilization—and our human language—we’ve “colonized” only certain small islands in the space of all possible concepts, leaving vast amounts of interconcept space unexplored.

What’s out there is pretty weird—and sometimes a bit disturbing. Here’s what we see zooming in on the same (randomly chosen) plane around “cat island” as above:

What are all these things? In a sense, words fail us. They’re things on the shores of interconcept space, where human experience has not (yet) taken us, and for which human language has not been developed.

What if we venture further out into interconcept space—and for example just sample points in the space at random? It’s just like we already saw above: we’ll get images that are somehow “statistically typical” of what we humans have put on the web, etc., and on which our AI was trained. Here are a few more examples:

And, yes, we can pick out at least two basic classes of images: ones that seem like “pure abstract textures”, and ones that seem “representational”, and remind us of real-world scenes from human experience. There are intermediate cases—like “textures” with structures that seem like they might “represent something”, and “representational-seeming” images where we just can’t place what they might be representing.

But when we do see recognizable “real-world-inspired” images they’re a curious reflection of the concepts—and general imagery—that we humans find “interesting enough to put on the web”. We’re not dealing here with some kind of “arbitrary interconcept space”; we’re dealing with “human-aligned” interconcept space that’s in a sense anchored to human concepts, but extends between and around them. And, yes, viewed in these terms it becomes quite unsurprising that in the interconcept space we’re sampling, there are so many images that remind us of human forms and common human situations.

But just what were the images that the AI saw, from which it formed this model of interconcept space? There were a few billion of them, “foraged” from the web. Like things on the web in general, it’s a motley collection; here’s a random sample:

Some can be thought of as capturing aspects of “life as it is”, but many are more aspirational, coming from staged and often promotionally oriented photography. And, yes, there are lots of Net-a-Porter-style “clothing-without-heads” images. There are also lots of images of “things”—like food, etc. But somehow when we sample randomly in interconcept space it’s the human forms that most distinctively stand out, conceivably because “things” are not particularly consistent in their structure, but human forms always have a certain consistency of “head-body-arms, etc.” structure.

It’s notable, though, that even the most real-world-like images we find by randomly sampling interconcept space seem to typically be “painterly” and “artistic” rather than “photorealistic” and “photographic”. It’s a different story close to “concept points”—like on cat island. There more photographic forms are common, though as we go away from the “actual concept point”, there’s a tendency towards either a rather toy-like appearance, or something more like an illustration.

By the way, even the most “photographic” images the AI generates won’t be anything that comes directly from the training set. Because—as we’ll discuss later—the AI is not set up to directly store images; instead its training process in effect “grinds up” images to extract their “statistical properties”. And while “statistical features” of the original images will show up in what the AI generates, any detailed arrangement of pixels in them is overwhelmingly unlikely to do so.

But, OK, what happens if we start not at a “describable concept” (like “a cat in a party hat”), but just at a random point in interconcept space? Here are the kinds of things we see:

The images often seem to be a bit more diverse than those around “known concept points” (like our “cat point” above). And occasionally there’ll be a “flash” of something “representationally familiar” (perhaps like a human form) that’ll show up. But most of the time we won’t be able to say “what these images are of”. They’re of things that are somehow “statistically” like what we’ve seen, but they’re not things that are familiar enough that we’ve—at least so far—developed a way to describe them, say with words.

The Images of Interconcept Space

There’s something strangely familiar—yet unfamiliar—to many of the images in interconcept space. It’s fairly common to see pictures that seem like they’re of people:

But they’re “not quite right”. And for us as humans, being particularly attuned to faces, it’s the faces that tend to seem the most wrong—even though other parts are “wrong” as well.

And perhaps in commentary on our nature as a social species (or maybe it’s as a social media species), there’s a great tendency to see pairs or larger groups of people:

There’s also a strange preponderance of torso-only pictures—presumably the result of “fashion shots” in the training data (and, yes, with some rather wild “fashion statements”):

People are by far the most common identifiable elements. But one does sometimes see other things too:

Then there are some landscape-type scenes:

Some look fairly photographically literal, but others build up the impression of landscapes from more abstract elements:

Occasionally there are cityscape-like pictures:

And—still more rarely—indoor-like scenes:

Then there are pictures that look like they’re “exteriors” of some kind:

It’s common to see images built up from lines or dots or otherwise “impressionistically formed”:

And then there are lots of images of that seem like they’re trying to be “of something”, but it’s not at all clear what that “thing” is, and whether indeed it’s something we humans would recognize, or whether instead it’s something somehow “fundamentally alien”:

It’s also quite common to see what look more like “pure patterns”—that don’t really seem like they’re “trying to be things”, but more come across like “decorative textures”:

But probably the single most common type of images are somewhat uniform textures, formed by repeating various simple elements, though usually with “dislocations” of various kinds:

Across interconcept space there’s tremendous variety to the images we see. Many have a certain artistic quality to them—and a feeling that they are some kind of “mindful interpretation” of a perhaps mundane thing in the world, or a simple, essentially mathematical pattern. And to some extent the “mind” involved is a collective version of our human one, reflected in a neural net that has “experienced” some of the many images humans have put on the web, etc. But in some ways the mind is also a more alien one, formed from the computational structure of the neural net, with its particular features, and no doubt in some ways computationally irreducible behavior.

And indeed there are some motifs that show up repeatedly that are presumably reflections of features of the underlying structure of the neural net. The “granulated” appearance, with alternation between light and dark, for example, is presumably a consequence of the dynamics of the convolutional parts of the neural net—and analogous to the results of what amounts to iterated blurring and sharpening with a certain effective pixel scale (reminiscent, for example, of video feedback):

Making Minds Alien

We can think of what we’ve done so far as exploring what a mind trained from human-like experiences can “imagine” by generalizing from those experiences. But what might a different kind of mind imagine?

As a very rough approximation, we can think of just taking the trained “mind” we’ve created, and explicitly modifying it, then seeing what it now “imagines”. Or, more specifically, we can take the neural net we have been using, and start making changes to it, and seeing what effect that has on the images it produces.

We’ll discuss later the details of how the network is set up, but suffice it to say here that it involves 391 distinct internal modules, involving altogether nearly a billion numerical weights. When the network is trained, those numerical weights are carefully tuned to achieve the results we want. But what if we just change them? We’ll still (normally) get a network that can generate images. But in some sense it’ll be “thinking differently”—so potentially the images will be different.

So as a very coarse first experiment—reminiscent of many that are done in biology—let’s just “knock out” each successive module in turn, setting all its weights to zero. If we ask the resulting network to generate a picture of “a cat in a party hat”, here’s what we now get:

Let’s look at these results in a bit more detail. In quite a few cases, zeroing out a single module doesn’t make much of a difference; for example, it might basically only change the facial expression of the cat:

But it can also more fundamentally change the cat (and its hat):

It can change the configuration or position of the cat (and, yes, some of those paws are not anatomically correct):

Zeroing out other modules can in effect change the “rendering” of the cat:

But in other cases things can get much more mixed up, and difficult for us to parse:

Sometimes there’s clearly a cat there, but its presentation is at best odd:

And sometimes we get images that have definite structure, but don’t seem to have anything to do with cats:

Then there are cases where we basically just get “noise”, albeit with things superimposed:

But—much like in neurophysiology—there are some modules (like the very first and last ones in our original list) where zeroing them out basically makes the system not work at all, and just generate “pure random noise”.

As we’ll discuss below, the whole neural net that we’re using has a fairly complex internal structure—for example, with a few fundamentally different kinds of modules. But here’s a sample of what happens if one zeros out modules at different places in the network—and what we see is that for the most part there’s no obvious correlation between where the module is, and what effect zeroing it out will have:

So far, we’ve just looked at what happens if we zero out a single module at a time. Here are some randomly chosen examples of what happens if one zeros out successively more modules (one might call this a “HAL experiment” in remembrance of the fate of the fictional HAL AI in the movie 2001):

And basically once the “catness” of the images is lost, things become more and more alien from there on out, ending either in apparent randomness, or sometimes barren “zeroness”.

Rather than zeroing out modules, we can instead randomize the weights in them (perhaps a bit like the effect of a tumor rather than a stroke in a brain)—but the results are usually at least qualitatively similar:

Something else we can do is just to progressively mix randomness uniformly into every weight in the network (perhaps a bit like globally “drugging” a brain). Here are three examples where in each case 0%, 1%, 2%, … of randomness was added—all “fading away” in a very similar way:

And similarly, we can progressively scale down towards zero (in 1% increments: 100%, 99%, 98%, …) all the weights in the network:

Or we can progressively increase the numerical values of the weights—eventually in some sense “blowing the mind” of the network (and going a bit “psychedelic” in the process):

Minds in Rulial Space

We can think of what we’ve done so far as exploring some of the “natural history” of what’s out there in generative AI space—or as providing a small taste of at least one approximation to the kind of mental imagery one might encounter in alien minds. But how does this fit into a more general picture of alien minds and what they might be like?

With the concept of the ruliad we finally have a principled way to talk about alien minds—at least at a theoretical level. And the key point is that any alien mind—or, for that matter, any mind—can be thought of as “observing” or sampling the ruliad from its own particular point of view, or in effect, its own position in rulial space.

The ruliad is defined to be the entangled limit of all possible computations: a unique object with an inevitable structure. And the idea is that anything—whether one interprets it as a phenomenon or an observer—must be part of the ruliad. The key to our Physics Project is then that “observers like us” have certain general characteristics. We are computationally bounded, with “finite minds” and limited sensory input. And we have a certain coherence that comes from our belief in our persistence in time, and our consistent thread of experience. And what we then discover in our Physics Project is the rather remarkable result that from these characteristics and the general properties of the ruliad alone it’s essentially inevitable that we must perceive the universe to exhibit the fundamental physical laws it does, in particular the three big theories of twentieth-century physics: general relativity, quantum mechanics and statistical mechanics.

But what about more detailed aspects of what we perceive? Well, that will depend on more detailed aspects of us as observers, and of how our minds are set up. And in a sense, each different possible mind can be thought of as existing in a certain place in rulial space. Different human minds are mostly close in rulial space, animal minds further away, and more alien minds still further. But how can we characterize what these minds are “thinking about”, or how these minds “perceive things”?

From inside our own minds we can form a sense of what we perceive. But we don’t really have good ways to reliably probe what another mind perceives. But what about what another mind imagines? Well, that’s where what we’ve been doing here comes in. Because with generative AI we’ve got a mechanism for exposing the “mental imagery” of an “AI mind”.

We could consider doing this with words and text, say with an LLM. But for us humans images have a certain fluidity that text does not. Our eyes and brains can perfectly well “see” and absorb images even if we don’t “understand” them. But it’s very difficult for us to absorb text that we don’t “understand”; it usually tends to seem just like a kind of “word soup”.

But, OK, so we generate “mental imagery” from “minds” that have been “made alien” by various modifications. How come we humans can understand anything such minds make? Well, it’s bit like one person being able to understand the thoughts of another. Their brains—and minds—are built differently. And their “internal view” of things will inevitably be different. But the crucial idea—that’s for example central to language—is that it’s possible to “package up” thoughts into something that can be “transported” to another mind. Whatever some particular internal thought might be, by the time we can express it with words in a language, it’s possible to communicate it to another mind that will “unpack” it into different internal thoughts.

It’s a nontrivial fact of physics that “pure motion” in physical space is possible; in other words, that an “object” can be moved “without change” from one place in physical space to another. And now, in a sense, we’re asking about pure motion in rulial space: can we move something “without change” from one mind at one place in rulial space to another mind at another place? In physical space, things like particles—as well as things like black holes—are the fundamental elements that are imagined to move without change. So what’s now the analog in rulial space? It seems to be concepts—as often, for example, represented by words.

So what does that mean for our exploration of generative AI “alien minds”? We can ask whether when we move from one potentially alien mind to another concepts are preserved. We don’t have a perfect proxy for this (though we could make a better one by appropriately training neural net classifiers). But as a first approximation this is like asking whether as we “change the mind”—or move in rulial space—we can still recognize the “concept” the mind produces. Or, in other words, if we start with a “mind” that’s generating a cat in a party hat, will we still recognize the concepts of cat or hat in what a “modified mind” produces?

And what we’ve seen is that sometimes we do, and sometimes we don’t. And for example when we looked at “cat island” we saw a certain boundary beyond which we could no longer recognize “catness” in the image that was produced. And by studying things like cat island (and particularly its analogs when not just the “prompt” but also the underlying neural net is changed) it should be possible to map out how far concepts “extend” across alien minds.

It’s also possible to think about a kind of inverse question: just what is the extent of a mind in rulial space? Or, in other words, what range of points of view, ultimately about the ruliad, can it hold? Will it be “narrow-minded”, able to think only in particular ways, with particular concepts? Or will it be more “broad-minded”, encompassing more ways of thinking, with more concepts?

In a sense the whole arc of the intellectual development of our civilization can be thought of as corresponding to an expansion in rulial space: with us progressively being able to think in new ways, and about new things. And as we expand in rulial space, we are in effect encompassing more of what we previously would have had to consider the domain of an alien mind.

When we look at images produced by generative AI away from the specifics of human experience—say in interconcept space, or with modified rules of generation—we may at first be able to make little from them. Like inkblots or arrangements of stars we’ll often find ourselves wanting to say that what we see looks like this or that thing we know.

But the real question is whether we can devise some way of describing what we see that allows us to build thoughts on what we see, or “reason” about it. And what’s very typical is that we manage to do this when we come up with a general “symbolic description” of what we see, say captured with words in natural language (or, now, computational language). Before we have those words, or that symbolic description, we’ll tend just not to absorb what we see.

And so, for example, even though nested patterns have always existed in nature, and were even explicitly created by mosaic artisans in the early 1200s, they seem to have never been systematically noticed or discussed at all until the latter part of the 20th century, when finally the framework of “fractals” was developed for talking about them.

And so it may be with many of the forms we’ve seen here. As of today, we have no name for them, no systematic framework for thinking about them, and no reason to view them as important. But particularly if the things we do repeatedly show us such forms, we’ll eventually come up with names for them, and start incorporating them into the domain that our minds cover.

And in a sense what we’ve done here can be thought of as showing us a preview of what’s out there in rulial space, in what’s currently the domain of alien minds. In the general exploration of ruliology, and the investigation of what arbitrary simple programs in the computational universe do, we’re able to jump far across the ruliad. But it’s typical that what we see is not something we can connect to things we’re familiar with. In what we’re doing here, we’re moving only much smaller distances in rulial space. We’re starting from generative AI that’s closely aligned with current human development—having been trained from images that we humans have put on the web, etc. But then we’re making small changes to our “AI mind”, and looking at what it now generates.

What we see is often surprising. But it’s still close enough to where we “currently are” in rulial space that we can—at least to some extent—absorb and reason about what we’re seeing. Still, the images often don’t “make sense” to us. And, yes, quite possibly the AI has invented something that has a rich and “meaningful” inner structure. But it’s just that we don’t (yet) have a way to talk about it—and if we did, it would immediately “make perfect sense” to us.

So if we see something we don’t understand, can we just “train a translator”? At some level the answer must be yes. Because the Principle of Computational Equivalence implies that ultimately there’s a fundamental uniformity to the ruliad. But the problem is that the translator is likely to have to do an irreducible amount of computational work. And so it won’t be implementable by a “mind like ours”. Still, even though we can’t create a “general translator” we can expect that certain features of what we see will still be translatable—in effect by exploiting certain pockets of computational reducibility that must necessarily exist even when the system as a whole is full of computational irreducibility. And operationally what this means in our case is that the AI may in effect have found certain regularities or patterns that we don’t happen to have noticed but that are useful in exploring further from the “current human point” in rulial space.

It’s very challenging to get an intuitive understanding of what rulial space is like. But the approach we’ve taken here is for me a promising first effort in “humanizing” rulial space, and seeing just how we might be able to relate to what is so far the domain of alien minds.

---

Appendix: How Does the Generative AI Work?

In the main part of this piece, we’ve mostly just talked about what generative AI does, not how it works inside. Here I’ll go a little deeper into what’s inside the particular type of generative AI system that I’ve used in my explorations. It’s a method called stable diffusion, and its operation is in many ways both clever and surprising. As it’s implemented today it’s steeped in fairly complicated engineering details. To what extent these will ultimately be necessary isn’t clear. But in any case here I’ll mostly concentrate on general principles, and on giving a broad outline of how generative AI can be used to produce images.

The Distribution of Typical Images

At the core of generative AI is the ability to produce things of some particular type that “follow the patterns of” known things of that type. So, for example, large language models (LLMs) are intended to produce text that “follows the patterns” of text written by humans, say on the web. And generative AI systems for images are similarly intended to produce images that “follow the patterns” of images put on the web, etc.

But what kinds of patterns exist in typical images, say on the web? Here are some examples of “typical images”—scaled down to 32×32 pixels and taken from a standard set of 60,000 images:

And as a very first thing, we can ask what colors show up in these images. They’re not uniform in RGB space:

But what about the positions of different colors? Adjusting to accentuate color differences, the “average image” turns out to have a curious “HAL’s eye” look (presumably with blue for sky at the top, and brown for earth at the bottom):

But just picking pixels separately—even with the color distribution inferred from actual images—won’t produce images that in any way look “natural” or “realistic”:

And the immediate issue is that the pixels aren’t really independent; most pixels in most images are correlated in color with nearby pixels. And in a first approximation one can capture this for example by fitting the list of colors of all the pixels to a multivariate Gaussian distribution with a covariance matrix that represents their correlation. Sampling from this distribution gives images like these—that indeed look somehow “statistically natural”, even if there isn’t appropriate detailed structure in them:

So, OK, how can one do better? The basic idea is to use neural nets, which can in effect encode detailed long-range connections between pixels. In some way it’s similar to what’s done in LLMs like ChatGPT—where one has to deal with long-range connections between words in text. But for images it’s structurally a bit more difficult, because in some sense one has to “consistently fit together 2D patches” rather than just progressively extend a 1D sequence.

And the typical way this is done at first seems a bit bizarre. The basic idea is to start with a random array of pixels—corresponding in effect to “pure noise”—and then progressively to “reduce the noise” to end up with a “reasonable image” that follows the patterns of typical images, all the while guided by some prompt that says what one wants the “reasonable image” to be of.

Attractors and Inverse Diffusion

How does one go from randomness to definite “reasonable” things? The key is to use the notion of attractors. In a very simple case, one might have a system—like this “mechanical” example—where from any “randomly chosen” initial condition one also evolves to one of (here) two definite (fixed-point) attractors:

One has something similar in a neural net that’s for example trained to recognize digits:

Regardless of exactly how each digit is written, or noise that gets added to it, the network will take this input and evolve to an attractor corresponding to a digit.

Sometimes there can be lots of attractors. Like in this (“class 2”) cellular automaton evolving down the page, many different initial conditions can lead to the same attractor, but there are many possible attractors, corresponding to different final patterns of stripes:

The same can be true for example in 2D cellular automata, where now the attractors can be thought of as being different “images” with structure determined by the cellular automaton rule:

But what if one wants to arrange to have particular images as attractors? Here’s where the somewhat surprising idea of “stable diffusion” can be used. Imagine we start with two possible images, and , and then in a series of steps progressively add noise to them:

Here’s the bizarre thing we now want to do: train a neural net to take the image we get at a particular step, and “go backwards”, removing noise from it. The neural net we’ll use for this is somewhat complicated, with “convolutional” pieces that basically operate on blocks of nearby pixels, and “transformers” that get applied with certain weights to more distant pixels. Schematically in Wolfram Language the network looks at a high level like this:

And roughly what it’s doing is to make an informationally compressed version of each image, and then to expand it again (through what is usually called a “U-net” neural net). We start with an untrained version of this network (say just randomly initialized). Then we feed it a couple of million examples of noisy pictures of and , and the denoised outputs we want in each case.

Then if we take the trained neural net and successively apply it, for example, to a “noised ”, the net will “correctly” determine that the “denoised” version is a “pure ”:

But what if we apply this network to pure noise? The network has been set up to always eventually evolve either to the “” attractor or the “” attractor. But which it “chooses” in a particular case will depend on the details of the initial noise—so in effect the network will seem to be picking at random to “fish” either “” or “” out of the noise:

How does this apply to our original goal of generating images “like” those found for example on the web? Well, instead of just training our “denoising” (or “inverse diffusion”) network on a couple of “target” images, let’s imagine we train it on billions of images from the web. And let’s also assume that our network isn’t big enough to store all those images in any kind of explicit way.

In the abstract it’s not clear what the network will do. But the remarkable empirical fact is that it seems to manage to successfully generate (“from noise”) images that “follow the general patterns” of the images it was trained from. There isn’t any clear way to “formally validate” this success. It’s really just a matter of human perception: to us the images (generally) “look right”.

It could be that with a different (alien?) system of perception we’d immediately see “something wrong” with the images. But for purposes of human perception, the neural net seems to give “reasonable-looking” images—perhaps not least because the neural net operates at least approximately like our brains and our processes of perception seem to operate.

Injecting a Prompt

We’ve described how a denoising neural net seems to be able to start from some configuration of random noise and generate a “reasonable-looking” image. And from any particular configuration of noise, a given neural net will always generate the same image. But there’s no way to tell what that image will be of; it’s just something to empirically explore, as we did above.

But what if we want to “guide” the neural net to generate an image that we’d describe as being of a definite thing, like “a cat in a party hat”? We could imagine “continually checking” whether the image we’re generating would be recognized by a neural net as being of what we wanted. And conceptually that’s what we can do. But we also need a way to “redirect” the image generation if it’s “not going in the right direction”. And a convenient way to do this is to mix a “description of what we want” right into the denoising training process. In particular, if we’re training to “recover an ”, mix a description of the “” right alongside the image of the “”.

And here we can make use of a key feature of neural nets: that ultimately they operate on arrays of (real) numbers. So whether they’re dealing with images composed of pixels, or text composed of words, all these things eventually have to be “ground up” into arrays of real numbers. And when a neural net is trained, what it’s ultimately “learning” is just how to appropriately transform these “disembodied” arrays of numbers.

There’s a fairly natural way to generate an array of numbers from an image: just take the triples of red, green and blue intensity values for each pixel. (Yes, we could pick a different detailed representation, but it’s not likely to matter—because the neural net can always effectively “learn a conversion”.) But what about a textual description, like “a cat in a party hat”?

We need to find a way to encode text as an array of numbers. And actually LLMs face the same issue, and we can solve it in basically the same way here as LLMs do. In the end what we want is to derive from any piece of text a “feature vector” consisting of an array of numbers that provide some kind of representation of the “effective meaning” of the text, or at least the “effective meaning” relevant to describing images.

Let’s say we train a neural net to reproduce associations between images and captions, as found for example on the web. If we feed this neural net an image, it’ll try to generate a caption for the image. If we feed the neural net a caption, it’s not realistic for it to generate a whole image. But we can look at the innards of the neural net and see the array of numbers it derived from the caption—and then use this as our feature vector. And the idea is that because captions that “mean the same thing” should be associated in the training set with “the same kind of images”, they should have similar feature vectors.

So now let’s say we want to generate a picture of a cat in a party hat. First we find the feature vector associated with the text “a cat in a party hat”. Then this is what we keep mixing in at each stage of denoising to guide the denoising process, and end up with an image that the image captioning network will identify as “a cat in a party hat”.

The Latent Space “Trick”

The most direct way to do “denoising” is to operate directly on the pixels in an image. But it turns out there’s a considerably more efficient approach, which operates not on pixels but on “features” of the image—or, more specifically, on a feature vector which describes an image.

In a “raw image” presented in terms of pixels, there’s a lot of redundancy—which is why, for example, image formats like JPEG and PNG manage to compress raw images so much without even noticeably modifying them for purposes of typical human perception. But with neural nets it’s possible to do much greater compression, particularly if all we want to do is to preserve the “meaning” of an image, without worrying about its precise details.

And in fact as part of training a neural net to associate images with captions, we can derive a “latent representation” of images, or in effect a feature vector that captures the “important features” of the image. And then we can do everything we’ve discussed so far directly on this latent representation—decoding it only at the end into the actual pixel representation of the image.

So what does it look like to build up the latent representation of an image? With the particular setup we’re using here, it turns out that the feature vector in the latent representation still preserves the basic spatial arrangement of the image. The “latent pixels” are much coarser than the “visible” ones, and happen to be characterized by 4 numbers rather than the 3 for RGB. But we can decode things to see the “denoising” process happening in terms of “latent pixels”:

And then we can take the latent representation we get, and once again use a trained neural net to fill in a “decoding” of this in terms of actual pixels, getting out our final generated image.

An Analogy in Simple Programs

Generative AI systems work by having attractors that are carefully constructed through training so that they correspond to “reasonable outputs”. A large part of what we’ve done above is to study what happens to these attractors when we change the internal parameters of the system (neural net weights, etc.). What we’ve seen has been complicated, and, indeed, often quite “alien looking”. But is there perhaps a simpler setup in which we can see similar core phenomena?

By the time we’re thinking about creating attractors for realistic images, etc. it’s inevitable that things are going to be complicated. But what if we look at systems with much simpler setups? For example, consider a dynamical system whose state is characterized just by a single number—such as an iterated map on the interval, like x a x (1 – x).

Starting from a uniform array of possible x values, we can show down the page which values of x are achieved at successive iterations:

For a = 2.9, the system evolves from any initial value to a single attractor, which consists of a single fixed final value. But if we change the “internal parameter” a to 3.1, we now get two distinct final values. And at the “bifurcation point” a = 3 there’s a sudden change from one to two distinct final values. And indeed in our generative AI system it’s fairly common to see similar discontinuous changes in behavior even when an internal parameter is continuously changed.

As another example—slightly closer to image generation—consider (as above) a 1D cellular automaton that exhibits class 2 behavior, and evolves from any initial state to some fixed final state that one can think of as an attractor for the system:

Which attractor one reaches depends on the initial condition one starts from. But—in analogy to our generative AI system—we can think of all the attractors as being “reasonable outputs” for the system. But now what happens if we change the parameters of the system, or in this case, the cellular automaton rule? In particular, what will happen to the attractors? It’s like what we did above in changing weights in a neural net—but a lot simpler.

The particular rule we’re using here has 4 possible colors for each cell, and is defined by just 64 discrete values from 0 to 3. So let’s say we randomly change just one of those values at a time. Here are some examples of what we get, always starting from the same initial condition as in the first picture above:

With a couple of exceptions these seem to produce results that are at least “roughly similar” to what we got without changing the rule. In analogy to what we did above, the cat might have changed, but it’s still more or less a cat. But let’s now try “progressive randomization”, where we modify successively more values in the definition of the rule. For a while we again get “roughly similar” results, but then—much like in our cat examples above—things eventually “fall apart” and we get “much more random” results:

One important difference between “stable diffusion” and cellular automata is that while in cellular automata, the evolution can lead to continued change forever, in stable diffusion there’s an annealing process used that always makes successive steps “progressively smaller”—and essentially forces a fixed point to be reached.

But notwithstanding this, we can try to get a closer analogy to image generation by looking (again as above) at 2D cellular automata. Here’s an example of the (not-too-exciting-as-images) “final states” reached from three different initial states in a particular rule:

And here’s what happens if one progressively changes the rule:

At first one still gets “reasonable-according-to-the-original-rule” final states. But if one changes the rule further, things get “more alien”, until they look to us quite random.

In changing the rule, one is in effect “moving in rulial space”. And by looking at how this works in cellular automata, one can get a certain amount of intuition. (Changes to the rule in a cellular automaton seem a bit like “changes to the genotype” in biology—with the behavior of the cellular automaton representing the corresponding “phenotype”.) But seeing how “rulial motion” works in a generative AI that’s been trained on “human-style input” gives a more accessible and humanized picture of what’s going on, even if it seems still further out of reach in terms of any kind of traditional explicit formalization.

Thanks

This project is the first I’ve been able to do with our new Wolfram Institute. I thank our Fourmilab Fellow Nik Murzin and Ruliad Fellow Richard Assar for help. I also thank Jeff Arle, Nicolò Monti, Philip Rosedale and the Wolfram Research Machine Learning Group.

Humanizing Multicomputational Processes

Multicomputation is one of the core ideas of the Wolfram Physics Project—and in particular is at the heart of our emerging understanding of quantum mechanics. But how can one get an intuition for what is initially the rather abstract idea of multicomputation? A good approach, I believe, is to see it in action in familiar systems and situations. And I explore here what seems like a particularly good example: games and puzzles.

One might not imagine that something as everyday as well-known games and puzzles would have any connection to the formalism for something like quantum mechanics. But the idea of multicomputation provides a link. And indeed one can view the very possibility of being able to have “interesting” games and puzzles as being related to a core phenomenon of multicomputation: multicomputational irreducibility.

In an ordinary computational system each state of the system has a unique successor, and ultimately there is a single thread of time that defines a process of computation. But in a multicomputational system the key idea is that states can have multiple successors—and tracing their behavior defines a whole multiway graph of branching and merging threads of time. And the point is that this is directly related to how one can think about typical games and puzzles.

Given a particular state of a game or puzzle, a player must typically decide what to do next. And where the idea of multicomputation comes in is that there are usually several choices that they can make. In any particular instance of the game, they’ll make a particular choice. But the point of the multicomputational paradigm is to look globally at the consequences of all possible choices—and to produce a multiway graph that represents them.

The notion of making what we call a multiway graph has actually existed—usually under the name of “game graphs”—for games and puzzles for a bit more than a hundred years. But with the multicomputational paradigm there are now some more general concepts that can be applied to these constructs. And in turn understanding the relation to games and puzzles has the potential to provide a new level of intuition and familiarity about multiway graphs.

My particular goal here is to investigate—fairly systematically—a sequence of well-known games and puzzles using the general methods we’ve been developing for studying multicomputational systems. As is typical in investigations that connect with everyday things, we’ll encounter all sorts of specific details. And while these may not immediately seem relevant to larger-scale discussions, they are important in our effort to provide a realistic and relatable picture of actual games and puzzles—and in allowing the connections we make with multicomputation to be on a solid foundation.

It’s worth mentioning that the possibility of relating games and puzzles to physics is basically something that wouldn’t make sense without our Physics Project. For games and puzzles are normally at some fundamental level discrete—especially in the way that they involve discrete branching of possibilities. And if one assumes physics is fundamentally continuous, there’s no reason to expect a connection. But a key idea of our Physics Project is that the physical world is at the lowest level discrete—like games and puzzles. And what’s more, our Physics Project posits that physics—like games and puzzles—has discrete possibilities to explore.

At the outset each of the games and puzzles I discuss here may seem rather different in their structure and operation. But what we’ll see is that when viewed in a multicomputational way, there is remarkable—and almost monotonous—uniformity across our different examples. I won’t comment too much on the significance of what we see until the end, when I’ll begin to discuss how various important multicomputational phenomena may play out in the context of games and puzzles. And how the very difficulty of conceptualizing multicomputation in straightforward human terms is what fundamentally leads to the engaging character of games and puzzles.

Tic-Tac-Toe

Consider a simplified version of tic-tac-toe (AKA “noughts and crosses”) played on a 2×2 board. Assume X plays first. Then one can represent the possible moves by the graph:

&#10005

On the next turn one gets:

&#10005

So far this graph is a simple tree. But if we play another turn we’ll see that different branches can merge, and “playing until the board is full” we get a multiway graph—or “game graph”—of the form:

&#10005

Every path through this graph represents a possible complete game:

&#10005

In our setup so far, the total number of board configurations that can ever be reached in any game (i.e. the total number of nodes in the graph) is 35, while the total number of possible complete games (i.e. the number of possible paths from the root of the graph) is 24.

If one renders the graph in 3D one can see that it has a very regular structure:

&#10005

And now if we define “winning” 2×2 tic-tac-toe as having two identical elements in a horizontal row, then we can annotate the multiway graph to indicate wins—removing cases where the “game is already over”:

&#10005

Much of the core structure of the multiway graph is actually already evident even in the seemingly trivial case of “one-player tic-tac-toe”, in which one is simply progressively filling in squares on the board:

&#10005

But what makes this not completely trivial is the existence of distinct paths that lead to equivalent states. Rendered differently the graph (which has 2⁴ = 16 nodes and 4! = 24 “game paths”) has an obvious 4D hypercube form (where now we have dropped the explicit X’s in each cell):

&#10005

For a 3×3 board the graph is a 9D hypercube with 2⁹ = 512 nodes and 9! = 362880 “game paths”, or in “move-layered” form:

&#10005

This basic structure is already visible in “1-player 1D tic-tac-toe” in which the multiway graph for a “length-n” board just corresponds to an n-dimensional hypercube:

&#10005

The total number of distinct board configurations in this case is just 2ⁿ, and the number of distinct “games” is n!. At move t the number of distinct board configurations (i.e. states) is Binomial[n, t].

With 2 players the graphs become slightly more complicated:

&#10005

The total number of states in these graphs is

&#10005

which is asymptotically . (Note that for n = 4 the result is the same as for the 2×2 board discussed above.) At move t the number of distinct states is given by

&#10005

&#10005

OK, so what about standard 2-player 3×3 tic-tac-toe? Its multiway graph begins:

&#10005

After 2 steps (i.e. one move by X and one by O) the graph is still a tree (with the initial state now at the center):

&#10005

After 3 steps there is starting to be merging:

&#10005

And continuing for all 9 moves the full layered graph—with 6046 states—is:

&#10005

At the level of this graph, the results are exactly the same as for a 2-player 1D version with a total of 9 squares. But for actual 2D 3×3 tic-tac-toe there is an additional element to the story: the concept of winning a game, and thereby terminating it. With the usual rules, a game is considered won when a player gets a horizontal, vertical or diagonal line of three squares, as in for example:

&#10005

Whenever a “win state” such as these is reached, the game is considered over, so that subsequent states in the multiway graph are pruned, and what was previously a 6046-node graph becomes a 5478-node graph

&#10005

with examples of the 568 pruned states including (where the “win” that terminated the game is marked):

&#10005

Wins can occur at different steps: anywhere from 5 to 9. The total numbers of distinct wins are as follows

&#10005

(yielding 626 wins at any step for X and 316 for O).

One can’t explicitly tell that a game has ended in a draw until every square has been filled in—and there are ultimately only 16 final “draw configurations” that can be reached:

&#10005

We can annotate the full (“game-over-pruned”) multiway graph, indicating win and draw states:

&#10005

To study this further, let’s start by looking at a subgraph that includes only “end games” starting with a board that already has 4 squares filled in:

&#10005

We see here that from our initial board

&#10005

it’s possible to get a final win for both X and O:

&#10005

But in many of these cases the outcome is already basically determined a step or more before the actual win occurs—in the sense that unless a given player “makes a mistake” they will always be able to force a win.

So, for example, if it is X’s turn and the state is

&#10005

then X is guaranteed to win if they play as follows:

&#10005

We can represent the “pre-forcing” of wins by coloring subgraphs (or in effect “light cones”) in the multiway graph:

&#10005

At the very beginning of the game, when X makes the first move, nothing is yet forced. But after just one move, it’s already possible to get to configurations where X can always force a win:

&#10005

Starting from a state obtained after 1 step, we can see that after 2 steps there are configurations where O can force a win:

&#10005

Going to more moves leads to more “forced-win” configurations:

&#10005

Annotating the whole multiway graph we get:

&#10005

We can think of this graph as a representation of the “solution” to the game: given any state the coloring in the graph tells us which player can force a win from that state, and the graph defines what moves they can make to do so.

Here’s a summary of possible game states at each move:

&#10005

&#10005

Here we’re just counting the number of possible states of various kinds at each step. But is there a way to think about these states as somehow being laid out in “game state space”? Branchial graphs provide a potential way to do this. The basic branchial graph at a particular step is obtained by joining pairs of states that share a common ancestor on the step before. For the case of 2-player 2×2 tic-tac-toe the branchial graphs we get on successive steps are as follows:

&#10005

Things get more complicated for ordinary 3×3 tic-tac-toe. But since the multiway graph for the first two steps is a pure tree, the branchial graphs at these steps still have a rather trivial structure:

&#10005

In general the number of connected components on successive steps is as follows

&#10005

and these are broken down across different graph structures as follows:

&#10005

Here in more detail are the forms of some typical components of branchial graphs achieved at particular steps:

&#10005

Within the branchial graph at a particular step, there can be different numbers of wins in different components:

&#10005

It’s notable that the wins are quite broadly distributed across branchial graphs. And this is in a sense why tic-tac-toe is not (more) trivial. If just by knowing what component of the branchial graph one was in one could immediately know the outcome, there would be even less “suspense” in the game. But with broad distribution across branchial space, “knowing roughly where you are” doesn’t help much in determining whether you’re going to win.

So far we’ve always been talking about what states can be reached, but not “how often” they’re reached. Imagine that rather than playing a specific game, we instead at each step just make every possible move with equal probability. The setup for tic-tac-toe is symmetrical enough that for most of the game the probability of every possible configuration at a given step is equal. But as soon as there start to be “wins”, and there is a “cone” of “game-over-pruned” states, then the remaining states no longer have equal probabilities.

For standard 3×3 tic-tac-toe this happens after 7 moves, where there are two classes of states, that occur with slightly different probabilities:

&#10005

At the end of the game, there are several classes of final states with different probabilities:

&#10005

And what this means for the probabilities of different outcomes of the game is as follows:

&#10005

Not surprisingly, the player who plays first has an advantage in winning. Perhaps more surprising is that in this kind of “strategyless” play, ties are comparatively uncommon—even though if one player actively tries to block the other, they often force a tie.

We’ve looked at “classic tic-tac-toe” and a few specific variants. But there are ultimately all sorts of possible variants. And a convenient general way to represent the “board” for any tic-tac-toe-like game is just to give a “flattened” list of values—with 0 representing a blank position, and i representing a symbol added by player i.

In standard “2D representation” one might have a board like

&#10005

which in flattened form would be:

&#10005

Typical winning patterns can then be represented

&#10005

where in each case we have framed the relevant “winning symbols”, and then given their positions in the flattened list. In ordinary tic-tac-toe it’s clear that the positions of “winning symbols” must always form an arithmetic progression. And it seems as if a good way to generalize tic-tac-toe is always to define a win for i to be associated with the presence of i symbols at positions that form an arithmetic progression of a certain length s. For ordinary tic-tac-toe s = 3, but for generalizations it could have other values.

Consider now the case of a length-5 list (i.e. 5-position “1D board”). The complete multiway graph is as follows, with “winning states” that contain arithmetic progressions of length s = 3 highlighted:

&#10005

In a more symmetrical rendering this is:

&#10005

Here’s the analogous result for a 7-position board, and 2 players:

&#10005

For each size of board n, we can compute the total number of winning states for any given player, as well as the total number of states altogether. The result when winning is based on arithmetic progressions of length 3 (i.e. s = 3) is:

&#10005

The 2-player n = 9 (= 3×3) case here is similar to ordinary tic-tac-toe, but not the same. In particular, states like

&#10005

are considered wins for X in the flattened setup, but not in ordinary tic-tac-toe.

If we increase the length of progression needed in order to declare a win, say to s = 4, we get:

&#10005

The total number of game states is unchanged, but—as expected—there are “fewer ways to win”.

But let’s say we have boards that are completely filled in. For small board sizes there may well not be an arithmetic progression of positions for any player—so that the game has to be considered a tie—as we see in this n = 5 case:

&#10005

But it is a result related to Ramsey theory that it turns out that for n ≥ 9, it’s inevitable that there will be an “arithmetic progression win” for at least one of the players—so that there is never a tie—as these examples illustrate:

&#10005

 

Walks and Their Multiway Graphs

A game like tic-tac-toe effectively involves at each step moving to one of several possible new board configurations—which we can think of as being at different “places” in “game state space”. But what if instead of board configurations we just consider our states to be positions on a lattice such as

&#10005

and then we look at possible walks, that at each step can, in this case, go one unit in any of 4 directions?

Starting at a particular point, the multiway graph after 1 step is just

&#10005

where we have laid out this graph so that the “states” are placed at their geometrical positions on the lattice.

After 2 steps we get:

&#10005

And in general the structure of the multiway graph just “recapitulates” the structure of the lattice:

&#10005

We can think of the paths in the multiway graph as representing all possible random walks of a certain length in the lattice. We can lay the graph out in 3D, with the vertical position representing the first step at which a given point can be reached:

&#10005

We can also lay out the graph more like we laid out multiway graphs for tic-tac-toe:

&#10005

One feature of these “random-walk” multiway graphs is that they contain loops, that record the possibility of “returning to places one’s already been”. And this is different from what happens for example in tic-tac-toe, in which at each step one is just adding an element to the board, and it’s never possible to go back.

But we can set up a similar “never-go-back rule” for walks, by considering “self-avoiding walks” in which any point that’s been visited can never be visited again. Let’s consider first the very trivial lattice:

&#10005

Now indicate the “current place we’ve reached” by a red dot, and the places we’ve visited before by blue dots—and start from one corner:

&#10005

There are only two possible walks here, one going clockwise, the other counterclockwise. Allowing one to start in each possible position yields a slightly more complicated multiway graph:

&#10005

With a 2×3 grid we get

&#10005

while with a 3×3 grid we get:

&#10005

Starting in the center, and with a different layout for the multiway graph, we get:

&#10005

Note the presence of large “holes”, in which paths on each side basically “get to the same place” in “opposite ways”. Note that of the 2304 possible ways to have 1 red dot and up to 8 blue ones, this actual multiway graph reaches only 57. (Starting from the corner reaches 75 and from all possible initial positions 438.)

With a 4×4 lattice (starting the walker in the corner) the multiway graph has the form

&#10005

or in an alternative layout

&#10005

where now 1677 states out of 524,288 are eventually visited, and the number of new states visited at each step (i.e. the number of nodes in successive layers in the graph) is:

&#10005

For a 5×5 grid 89,961 states are reached, distributed across steps according to:

&#10005

(For a grid with n vertices, there are a total of n 2^n–1 possible states, but the number actually reached is always much smaller.)

In talking about walks, an obvious question to ask is about mazes. Consider the maze:

&#10005

As far as traversing this maze is concerned, it is equivalent to “walking” on the graph

&#10005

which in another embedding is just

&#10005

But just as before, the multiway graph that represents all possible walks essentially just “recapitulates” this graph. And that means that “solving” the maze can in a sense equally be thought of as finding a path directly in the maze graph, or in the multiway graph:

&#10005

 

The Icosian Game & Some Relatives

Our discussion of self-avoiding walks turns out to be immediately related to the “Icosian game” of William Rowan Hamilton from 1857 (which is somewhat related to the early computer game Hunt the Wumpus):

The object of the “game” (or, more properly, puzzle) is to find a path (yes, a Hamiltonian path) around the icosahedron graph that visits every node (and returns back to where it started from). And once again we can construct a multiway graph that represents all possible sequences of “moves” in the game.

Let’s start with the simpler case of an underlying tetrahedron graph:

&#10005

From this we get the multiway graph:

&#10005

The “combined multiway graph” from all possible starting positions on the tetrahedron graph gives a truncated cuboctahedron multiway graph:

&#10005

And following this graph we see that from any initial state it’s always possible to reach a state where every node in the tetrahedron graph has been visited. In fact, because the tetrahedron graph is a complete graph it’s even guaranteed that the last node in the sequence will be “adjacent” to the starting node—so that one has formed a Hamiltonian cycle and solved the puzzle.

Things are less trivial for the cube graph:

&#10005

The multiway graph (starting from a particular state) in this case is:

&#10005

Now there are 13 configurations where no further moves are possible:

&#10005

In some of these, one’s effectively “boxed in” with no adjacent node to visit. In others, all the nodes have been filled in. But only 3 ultimately achieve a true Hamiltonian cycle that ends adjacent to the starting node:

&#10005

It turns out that one can reach each of these states through 4 distinct paths from the root of the multiway graph. An example of such a path is:

&#10005

We can summarize this path as a Hamiltonian circuit of the original cube graph:

&#10005

In the multiway graph, the 12 “winning paths” are

&#10005

In a different rendering this becomes

&#10005

and keeping only “winning paths” the subgraph of the multiway graph has the symmetrical form:

&#10005

The actual Hamiltonian circuits through the underlying cube graph corresponding to these winning paths are:

&#10005

For the dodecahedral graph (i.e. the original Icosian game), the multiway graph is larger and more complicated. It begins

&#10005

and has its first merge after 11 steps (and 529 in all), and ends up with a total of 11,093 nodes—of which 2446 are “end states” where no further move is possible. This shows the number of end (below) and non-end (above) states at each successive step:

&#10005

The successive fractions of “on-track-to-succeed” states are as follows, indicating that the puzzle is in a sense harder at the beginning than at the end:

&#10005

There are 13 “end states” which fill in every position of the underlying dodecahedral graph, with 3 of these corresponding to Hamiltonian cycles:

&#10005

The total number of paths from the root of the multiway graph leading to end states (in effect the total number of ways to try to solve the puzzle) is 3120. Of these, 60 lead to the 3 Hamiltonian cycle end states. An example of one of these “winning paths” is:

&#10005

Examples of underlying Hamiltonian cycles corresponding to each of the 3 Hamiltonian cycle end states are:

&#10005

And this now shows all 60 paths through the multiway graph that reach Hamiltonian cycle end states—and thus correspond to solutions to the puzzle:

&#10005

In effect, solving the puzzle consists in successfully finding these paths out of all the possibilities in the multiway graph. In practice, though—much as in theorem-proving, for example—there are considerably more efficient ways to find “winning paths” than to look directly at all possibilities in the multiway graph (e.g. FindHamiltonianCycle in Wolfram Language). But for our purpose of understanding games and puzzles in a multicomputational framework, it’s useful to see how solutions to this puzzle lay out in the multiway graph.

The Icosian game from Hamilton was what launched the idea of Hamiltonian cycles on graphs. But already in 1736 Leonhard Euler had discussed what are now called Eulerian cycles in connection with the puzzle of the Bridges of Königsberg. In modern terms, we can state the puzzle as the problem of finding a path that visits once and only once all the edges in the graph (in which the “double bridges” from the original puzzle have been disambiguated by extra nodes):

&#10005

We can create a multiway graph that represents all possible paths starting from a particular vertex:

&#10005

But now we see that the end states here are

&#10005

and since none of them have visited every edge, there is no Eulerian circuit here. To completely resolve the puzzle we need to make a multiway graph in which we start from all possible underlying vertices. The result is a disconnected multiway graph whose end states again never visit every edge in the underlying graph (as one can tell from the fact that the number of “levels” in each subgraph is less than 10):

&#10005

 

The Geography Game

In the Geography Game one has a collection of words (say place names) and then one attempts to “string the words together”, with the last letter of one word being the same as the first letter of the next. The game typically ends when nobody can come up with a word that works and hasn’t been used before.

Usually in practice the game is played with multiple players. But one can perfectly well consider a version with just one player. And as an example let’s take our “words” to be the abbreviations for the states in the US. Then we can make a graph of what can follow what:

&#10005

Let’s at first ignore the question of whether a state has “already been used”. Then, starting, say, from Massachusetts (MA), we can construct the beginning of a multiway graph that gives us all possible sequences:

&#10005

After 10 steps the graph is

&#10005

or in a different rendering:

&#10005

This shows the total number of paths as a function of length through this graph, assuming one doesn’t allow any state to be repeated:

&#10005

The maximum length of path is 23—and there are 256 such paths, 88 ending with TX and 168 ending with AZ. A few sample such paths are

&#10005

and all these paths can be represented by what amounts to a finite state machine:

&#10005

By the way, the starting state that leads to the longest path is MN—which achieves length 24 in 2336 different ways, with possible endings being AZ, DE, KY and TX. A few samples are:

&#10005

Drawing these paths in the first few steps of the multiway graph starting from MN we get:

&#10005

 

Groups and (Simplified) Rubik’s Cubes

We’ve talked about puzzles that effectively involve walks on graphs. A particularly famous example of a puzzle that can be thought about in this way is the Rubik’s Cube. The graph in question is then the Cayley graph for the group formed by the transformations that can be applied to the cube.

As a very simple analog, we can consider the symmetry group of the square, D₄, based on the operations of reflection and 90° rotation. We generate the Cayley graph just like a multiway graph: by applying each operation at each step. And in this example the Cayley graph is:

&#10005

This graph is small enough that it is straightforward to see how to get from any configuration to any other. But while this Cayley graph has 8 nodes and maximum path length from any one node to any other of 3, the Cayley graph for the Rubik’s Cube has nodes and a maximum shortest path length of 20.

To get some sense of the structure of an object like this, we can consider the very simplified case of a “2×2×2 cube”—colored only on its corners—in which each face can be rotated by 90°:

&#10005

The first step in the multiway graph—starting from the configuration above—is then (note that the edges in the graph are not directed, since the underlying transformations are always reversible):

&#10005

Going another step gives:

&#10005

The complete multiway graph (which is also the Cayley graph for the group—which turns out to be S₈—generated by the transformations) has 8! = 40,320 nodes (and 483,840 edges). Starting from a state (i.e. node in the Cayley graph) the number of new states reached at successive steps is:

&#10005

The maximum shortest paths in the graph consist of 8 steps; an example is:

&#10005

Between these particular two endpoints there are actually 3216 “geodesic” paths—which spread out quite far in the multiway graph

&#10005

Picking out only geodesic paths we see there are many ways to get from one configuration of the cube to one of its “antipodes”:

&#10005

 

Peg Solitaire

Whereas something like tic-tac-toe involves progressively filling in a board, a large class of puzzles that have been used since at least the 1600s involve basically removing pegs from a board. The typical rules involve pegs being able to jump over a single intermediate peg into a hole, with the intermediate peg then being removed. The goal is to end up with just a single peg on the board.

Here’s a very simple example based on a T arrangement of pegs:

&#10005

In this case, there’s only one way to “solve the puzzle”. But in general there’s a multiway graph:

&#10005

A more complicated example is the “Tricky Triangle” (AKA the “Cracker Barrel puzzle”). Its multiway graph begins:

&#10005

After another couple of steps it becomes:

&#10005

There are a total of 3016 states in the final multiway graph, of which 118 are “dead-end” configurations from which no further moves are possible. The “earliest” of these dead-end configurations are:

&#10005

There are just 4 “winning states” that can be reached, and the “end games” that lead to them are:

&#10005

Starting from the initial configuration, the number of possible states reached at each step is given as follows, where the states that can lead to winning configurations is shown in yellow:

&#10005

This shows the complete multiway graph, with “winning paths” highlighted:

&#10005

At successive steps, the fraction of states that can lead to a winning state is as follows:

&#10005

The branchial graphs are highly connected, implying that in a sense the puzzle remains “well mixed” and “unpredictable” until the very end:

&#10005

 

Checkers

Peg solitaire is a one-player “game”. Checkers (AKA draughts) is a two-player game with a somewhat similar setup. “Black” and “red” pieces move diagonally in different directions on a board, “taking” each other by jumping over when they are adjacent.

Let’s consider the rather minimal example of a 4×4 board. The basic set of possible moves for “black” and “red” is defined by the graphs (note that a 4×4 board is too small to support “multiple jumps”):

&#10005

With this setup we can immediately start to generate a multiway graph, based on alternating black and red moves:

&#10005

With the rules as defined so far, the full 161-node multiway graph is:

&#10005

It’s not completely clear what it means to “win” in this simple 4×4 case. But one possibility is to say that it happens when the other player can’t do anything at their next move. This corresponds to “dead ends” in the multiway graph. There are 26 of these, of which only 3 occur when it is red’s move next, and the rest all occur when it is black’s move:

&#10005

As before, any particular checkers game corresponds to a path in the multiway graph from the root to one of these end states. If we look at branchial graphs in this case, we find that they have many disconnected pieces, indicating that there are many largely independent “game paths” for this simple game—so there is not much “mixing” of outcomes:

&#10005

&#10005

The rules we’ve used so far don’t account for what amounts to the second level of rules for checkers: the fact that when a piece reaches the other side of the board it becomes a “king” that’s allowed to move backwards as well as forwards. Even with a single piece and single player this already generates a multiway graph—notably now with loops:

&#10005

or in an alternative layout (with explicitly undirected edges):

&#10005

With two pieces (and two players taking turns) the “kings” multiway graph begins:

&#10005

With this initial configuration, but without backward motion, the whole multiway graph is just:

&#10005

The full “kings” multiway graph in this case also only has 62 nodes—but includes all sorts of loops (though with this few pieces and black playing first it’s inevitable that any win will be for black):

&#10005

What about the ordinary + kings multiway graph from our original initial conditions? The combined graph has 161 nodes from the “pre-king” phase, and 4302 from the “post-king” phase—giving the final form:

&#10005

 

(Very Simplified) Go

The full game of Go is sophisticated and its multiway graph in any realistic case is far too big for us to generate at all explicitly (though one can certainly wonder if there are meaningful “continuum limit” results). However, to get some flavor of Go we can consider a vastly simplified version in which black and white “stones” are progressively placed on nodes of a graph, and the game is considered “won” if one player has successfully surrounded a connected collection of the other player’s stones.

Imagine that we start with a blank “board” consisting of a 2×2 square of positions, then on a sequence of “turns” add black and white stones in all possible ways. The resulting multiway graph is:

&#10005

Every state that has no successor here is a win for either black or white. The “black wins” (with the surrounded stone highlighted) are

&#10005

while the “white wins” are:

&#10005

At this level what we have is basically equivalent to 2×2 tic-tac-toe, albeit with a “diagonal” win condition. With a 3×2 “board”, the first two steps in the multiway graph are:

&#10005

The final multiway graph is:

&#10005

The graph has 235 nodes, of which 24 are wins for white, and 34 for black:

&#10005

The successive branchial graphs in this case are (with wins for black and white indicated):

&#10005

For a 3×3 “board” the multiway graph has 5172 states, with 604 being wins for white and 684 being wins for black.

Nim

As another example of a simple game, we’ll now consider Nim. In Nim, there are k piles of objects, and at each step p players alternate in removing as many objects as they want from whatever single pile they choose. The loser of the game is the player who is forced to have 0 objects in all the piles.

Starting off with 2 piles each containing 2 objects, one can construct a multiway graph for the game:

&#10005

With 3 piles this becomes:

&#10005

These graphs show all the different possible moves that relate different configurations of the piles. However, they do not indicate which player moves when. Adding this we get in the 22 case

&#10005

and in the 222 case:

&#10005

Even though these graphs look somewhat complicated, it turns out there is a very straightforward criterion for when a particular state has the property that its “opponent” can force a lose: just take the list of numbers and see if Apply[BitXor, list] is 0. Highlighting when this occurs we get:

&#10005

It turns that for Nim, the sequence of branchial graphs we get have a rather regular structure. In the 22 case, with the same highlighting as before, we get:

&#10005

In the 222 case the sequence of branchial graphs becomes:

&#10005

Here are results for some other cases:

&#10005

 

Sliding Block Puzzles

They go under many names—with many different kinds of theming. But many puzzles are ultimately sliding block puzzles. A simple example might ask to go from

&#10005

by sliding blocks into the empty (darker) square. A solution to this is:

&#10005

One can use a multiway graph to represent all possible transformations:

&#10005

(Note that only 12 of the 4! = 24 possible configurations of the blocks appear here; a configuration like cannot be reached.)

Since blocks can always be “slid both ways” every edge in a sliding-block-puzzle multiway graph has an inverse—so going forward we’ll just draw these multiway graphs as undirected.

Here are some simple cases:

&#10005

&#10005

With a 3×2 board, things quickly get more complicated:

&#10005

Rendered in 3D this becomes:

&#10005

When all the blocks are distinct, one tends to get multiway graphs with a kind of spherical structure:

&#10005

(Note that in the first three cases here, it’s possible to reach all 30, 120, 360 conceivable arrangements of the blocks, while in the last case one can only reach “even permutations” of the blocks, or 360 of the 720 conceivable arrangements.)

This shows how one gets from to :

&#10005

With many identical blocks one tends to build up a simple lattice:

&#10005

Making one block different basically just “adds decoration”:

&#10005

As the number of “1” and “2” blocks becomes closer to equal, the structure fills in:

&#10005

Adding a third type of block rapidly leads to a very complicated structure:

&#10005

This summarizes a few of the graphs obtained:

&#10005

&#10005

 

Towers of Hanoi, etc.

Another well-known puzzle is the Towers of Hanoi. And once again we can construct a multiway graph for it. Starting with all disks on the left peg the first step in the multiway graph is:

&#10005

Going two steps we get:

&#10005

The complete multiway graph is then (showing undirected edges in place of pairs of directed edges):

&#10005

It is rather easy to see how the recursive structure of this multiway graph builds up. Here’s the “base case” of 2 disks (and 3 pegs):

&#10005

And as each disk is added, the number of nodes in the multiway graph increases by a factor of 3—yielding for example with 4 disks (and still 3 pegs):

&#10005

With 4 pegs, things at first look more complicated, even with 2 disks:

&#10005

In a 3D rendering, more structure begins to emerge:

&#10005

And here are the results for 3, 4 and 5 disks—with the “points of the ears” corresponding to states where all the disks are on a single peg:

&#10005

With 3 pegs, the shortest “solution to the puzzle”—of moving all disks from one peg to another—goes along the “side” of the multiway graph, and for n pegs is of length 2ⁿ – 1:

&#10005

With 4 pegs, there is no longer a unique “geodesic path”:

&#10005

(And the sequence of path lengths for successive numbers of pegs is

&#10005

or a little below for a large number of pegs n.)

What about branchial graphs? For the standard 3-disk 3-peg case we have

&#10005

where successive “time slices” are assumed to be obtained by looking at successive vertical levels in the rendering of the multiway graph above.

For 4 disks one essentially gets “more of the same”:

&#10005

With 4 pegs things become slightly more complicated:

&#10005

And the trend continues for 5 pegs:

&#10005

 

Multicomputational Implications & Interpretation

We’ve now gone through many examples of games and puzzles. And in each case we’ve explored the multiway graphs that encapsulate the whole spectrum of their possible behavior. So what do we conclude? The most obvious point is that when games and puzzles seem to us difficult—and potentially “interesting”—it’s some kind of reflection of apparent complexity in the multiway graph. Or, put another way, it’s when we find the multiway graph somehow “difficult to decode” that we get a rich and engaging game or puzzle.

In any particular instance of playing a game we’re basically following a specific path (that in analogy to physics we can call a “timelike path”) through the multiway graph (or “game graph”) for the game. And at some level we might just make the global statement that the game graph represents all such paths. But what the multicomputational paradigm suggests is that there are also more local statements that we can usefully make. In particular, at every step along a timelike path we can look “transversally” in the multiway graph, and see the “instantaneous branchial graph” that represents the “entanglement” of our path with “nearby paths”.

Figuring out “what move to make next” is then in a sense about deciding in “what direction” in branchial space to go. And what makes a game difficult is that we can’t readily predict what happens as we “travel through branchial space”. There’s a certain analogy here to the concept of computational irreducibility. Going from one state to another along some timelike path, computational irreducibility implies that even though we may know the underlying rules, we can’t readily predict their consequences—because it can require an irreducible amount of computation to figure out what their consequences will be after many steps.

Predicting “across branchial space” is a related, but slightly different phenomenon, that one can describe as “multicomputational irreducibility”. It’s not about the difficulty of working out a particular path of computation, but instead about the difficulty of seeing how many entangled paths interact.

When one plays a game, it’s common to talk about “how many moves ahead one can see”. And in our terms here, this is basically about asking how “far out in branchial space” we can readily get. As computationally bounded entities, we have a certain “reach” in branchial space. And the game is “difficult for us” if that reach isn’t sufficient to be able to get to something like a “winning position”.

There’s another point here, though. What counts as “winning” in a game is typically reaching some particular places or regions in the multiway graph. But the definition of these places or regions is typically something very computationally bounded (“just see if there’s a line of X’s”, etc.). It’s a certain “observation” of the system, that extracts just a particular (computationally bounded) sampling of the complete state. And then what’s key is that this sampling doesn’t manage to “decode the multicomputational irreducibility”.

There’s an analogy here to thermodynamics. The fact that in thermodynamics we perceive “heat” and “entropy increase” is a consequence of the fact that our (coarse-grained) measurements can’t “decode” the computationally irreducible process that leads to the particular states generated in the system. Similarly, the fact we perceive it to be “hard to figure out how to win a game” is a consequence of the fact that our criterion for winning isn’t able to “look inside the playing of the game” and “decode what’s going on” to the point where it’s in effect just selecting one particular, straightforward path. Instead it’s a question of going through the multicomputationally irreducible process of playing the game, and in effect “seeing where it lands” relative to the observation of winning.

There’s also an analogy here to quantum mechanics. Tracing through many possible paths of playing a game is like following many threads of history in quantum mechanics, and the criterion of winning is like a quantum measurement that selects certain threads. In our Physics Project we imagine that we as observers are extended in branchial space, “knitting together” different threads of history through our belief in our own single thread of experience. In games, the analog of our belief in a single thread of experience is presumably in effect that “all that matters is who wins or loses; it doesn’t matter how the game is played inside”.

To make a closer analogy with quantum mechanics one can start thinking about combining different chunks of “multiway game play”, and trying to work out a calculus for how those chunks fit together.

The games we’ve discussed here are all in a sense pure “games of skill”. But in games where there’s also an element of chance we can think of this as causing what is otherwise a single path in the multiway graph to “fuzz out” into a bundle of paths, and what is otherwise a single point in branchial space to become a whole extended region.

In studying different specific games and puzzles, we’ve often had to look at rather simplified cases in order to get multiway graphs of manageable size. But if we look at very large multiway graphs, are there perhaps overall regularities that will emerge? Is there potentially some kind of “continuum limit” for game graphs?

It’ll almost inevitably be the case that if we look in “enough detail” we’ll see all sorts of multicomputational irreducibility in action. But in our Physics Project—and indeed in the multicomputational paradigm in general—a key issue is that relevant observers don’t see that level of detail. And much like the emergence of thermodynamics or the gas laws from underlying molecular dynamics, the very existence of underlying computational irreducibility inevitably leads to simple laws for what the observer can perceive.

So what is the analog of “the observer” for a game? For at least some purposes it can be thought of as basically the “win” criteria. So now the question arises: if we look only at these criteria, can we derive the analog of “laws of physics”, insensitive to all the multicomputationally irreducible details underneath?

There’s much more to figure out about this, but perhaps one place to start is to look at the large-scale structure of branchial space—and the multiway graph—in various games. And one basic impression in many different games is that—while the character of branchial graphs may change between “different stages” in the game—across a single branchial graph there tends to be a certain uniformity. If one looks at the details there may be plenty of multicomputational irreducibility. But at some kind of “perceptible level” different parts of the graph may seem similar. And this suggests that the “local impression of the game” will tend to be similar at a particular stage even when quite different moves have been made, that take one to quite different parts of the “game space” defined by the branchial graph.

But while there may be similarity between different parts of the branchial graph, what we’ve seen is that in some games and puzzles the branchial graph breaks up into multiple disconnected regions. And what this reflects is the presence of distinct “conserved sectors” in a game—regions of game space that players can get into, but are then stuck with (at least for a certain time), much as in spacetime event horizons can prevent transport between different regions of physical space.

Another (related) effect that we notice in some games and puzzles but not others is large “holes” in the multiway graph: places where between two points in the graph there are multiple “distant” paths. When the multiway graph is densely connected, there’ll typically always be a way to “fix any mistake” by rerouting through nearby paths. But when there is a hole it is a sign that one can end up getting “committed” to one course of action rather than another, and it will be many steps before it’s possible to get to the same place as the other course of action would have reached.

If we assume that at some level all we ultimately “observe” in the multiway graph is the kind of coarse-graining that corresponds to assessing winning or losing then inevitably we’ll be dealing with a distribution of possible paths. Without “holes” these paths can be close together, and may seem obviously similar. But when there’s a hole there can be different paths that are far apart. And the fact there can be distant paths that are “part of the same distribution” can then potentially be thought of as something like a quantum superposition effect.

Are there analogs of general relativity and the path integral in games? To formulate this with clarity we’d have to define more carefully the character of “game space”. Presumably there’ll be the analog of a causal graph. And presumably there’ll also be an analog of energy in game space, associated with the “density of activity” at different places in game space. Then the analog of the phenomenon of gravity will be something like that the best game plays (i.e. the geodesic paths through the game graph) will tend to be deflected by the presence of high densities of activity. In other words, if there are lots of things to do when a game is in a certain state, good game plays will tend to be “pulled towards that state”. And at some level this isn’t surprising: when there’s high density of activity in the game graph, there will tend to be more options about what to do, so it’s more likely that one will be able to “do a good game play” if one goes through there.

So far we didn’t explicitly talk about strategies for games. But in our multicomputational framework a strategy has a fairly definite interpretation: it is a place in rulial space, where in effect one’s assuming a certain set of rules about how to construct the multiway graph. In other words, given a strategy one is choosing some edges in the multiway graph (or some possible events in the associated multiway causal graph), and dropping others.

In general it can be hard to talk about the “space of possible strategies”—because it’s like talking about the “space of possible programs”. But this is precisely what rulial space lets us talk about. What exact “geometry” the “space of strategies” has will depend on how we choose to coordinatize rulial space. But once again there will tend to be a certain level of coarse-graining achieved by looking only at the kinds of things one discusses in game theory—and at this level we can expect that all sorts of standard “structural” game-theoretic results will generically hold.

Personal Notes

Even as a kid I was never particularly into playing games or doing puzzles. And maybe it’s a sign I was always a bit too much of a scientist. Because just picking specific moves always seemed to me too arbitrary. To get my interest I needed a bigger picture, more of a coherent intellectual story. But now, in a sense, that’s just what the multicomputational approach to games and puzzles that I discuss here is bringing to us. Yes, it’s very “humanizing” to be able think about making particular moves. But the multicomputational approach immediately gives one a coherent global view that, at least to me, is intellectually much more satisfying.

The explorations I’ve discussed here can be thought of as originating from a single note in A New Kind of Science. In Chapter 5 of A New Kind of Science I had a section where I first introduced multiway systems. And as the very last note for that section I discussed “Game systems”:

&#10005

I did the research for this in the 1990s—and indeed I now find a notebook from 1998 about tic-tac-toe with some of the same results derived here

&#10005

together with a curious-looking graphical representation of the tic-tac-toe game graph:

&#10005

But back at that time I didn’t conclude much from the game graphs I generated; they just seemed large and complicated. Twenty years passed and I didn’t think much more about this. But then in 2017 my son Christopher was playing with a puzzle called Rush Hour:

And perhaps in a sign of familial tendency he decided to construct its game graph—coming up with what to me seemed like a very surprising result:

&#10005

At the time I didn’t try to understand the structure one has here—but I still “filed this away” as evidence that game graphs can have “visible large-scale structure”.

A couple of years later—in late 2019—our Physics Project was underway and we’d realized that there are deep relations between quantum mechanics and multiway graphs. Quantum mechanics had always seemed like something mysterious—the abstract result of pure mathematical formalism. But seeing the connection to multiway systems began to suggest that one might actually be able to “understand quantum mechanics” as something that could “mechanically arise” from some concrete underlying structure.

I started to think about finding ways to explain quantum mechanics at an intuitive level. And for that I needed a familiar analogy: something everyday that one could connect to multiway systems. I immediately thought about games. And in September 2020 I decided to take a look at games to explore this analogy in more detail. I quickly analyzed games like tic-tac-toe and Nim—as well as simple sliding block puzzles and the Towers of Hanoi. But I wanted to explore more games and puzzles. And I had other projects to do, so the multicomputational analysis of games and puzzles got set aside. The Towers of Hanoi reappeared earlier this year, when I used it as an example of generating a proof-like multiway graph, in connection with my study of the physicalization of metamathematics. And finally, a few weeks ago I decided it was time to write down what I knew so far about games and puzzles—and produce what’s here.

Thanks

Thanks to Brad Klee and Ed Pegg for extensive help in the final stages of the analysis given here—as well as to Christopher Wolfram for inspiration in 2017, and help in 2020.

The Nature of Alien Intelligence

“We’re going to launch lots of tiny spacecraft into interstellar space, have them discover alien intelligence, then bring back its technology to advance human technology by a million years”. I’ve heard some pretty wacky startup pitches over the years, but this might possibly be the all-time winner.

But as I thought about it, I realized that beyond the “absurdly extreme moonshot” character of this pitch, there’s some science that I’ve done that makes it clear that it’s also fundamentally philosophically confused. The nature of the confusion is interesting, however, and untangling it will give us an opportunity to illuminate some deep features of both intelligence and technology—and in the end suggest a way to think about the long-term trajectory of the very concept of technology and its relation to our universe.

Let’s start with a scenario. Let’s say one of the little spacecraft comes across a planet where it sees complicated swirling patterns:

&#10005

The spacecraft sends out a probe to “make contact”. The swirling pattern “responds” by changing slightly. The spacecraft analyzes the change, and sends out another probe. And pretty soon there’s a whole “conversation” going on between the spacecraft and the planet. But, you might say, that’s nothing like an “intelligence” there; there’s just a “pure physical system” that operates through physical laws.

OK, but now let’s imagine the spacecraft has returned to Earth and is checking it out. It detects complicated patterns of radio signals. It sends out a radio signal of its own. Something on Earth responds. A “conversation” ensues. Maybe the spacecraft is “talking to” a cellphone tower, doing automated handshakes with it. Maybe it reached a ham radio operator, and is exchanging Morse code with them. Or maybe—in an ultimate version of code injection—there’s a computer that’s interpreting the spacecraft’s signals as a program, and is sending back the results of running the program.

It all seems quite sophisticated—and at some level worthy of the technological civilization we’ve built up here on Earth. But let’s zoom out a bit. There’s something coming from the spacecraft, that’s causing something to happen on Earth, that’s causing something to be returned to the spacecraft.

And ultimately whatever is happening on Earth must be a physical process of some kind—operating according to the laws of physics. So what’s the difference between this and those swirling “just physics” patterns that the spacecraft found on the other planet? Everything is ultimately “just physics” after all.

OK, you might say, that’s surely true. But on Earth, even though we might have started from physics, we’ve somehow now “ascended” through chemistry and biology and technology to get to something that’s fundamentally more sophisticated. But here we run into an important—if at first surprising—piece of basic science: my Principle of Computational Equivalence.

Let’s say we represent all those “physical processes” as computations (and our Physics Project implies that all of physics is indeed ultimately computational). Now we can compare the computations that correspond to the planet with the swirling patterns to the ones that correspond to our Earth with us humans in the loop.

And what the Principle of Computational Equivalence tells us is that they’re ultimately equivalent. The computations associated with the swirling patterns are ultimately just as sophisticated as the ones we achieve with our brains and our technology here on Earth. It’s far from obvious that this would be true. But it’s something one discovers when one explores the computational universe of possible programs.

One might think that simple programs would produce only simple behavior, and that somehow the behavior would get progressively more complex with more complicated programs. But that’s not what one finds. Instead, there’s increasing evidence that almost any program that doesn’t show obviously simple behavior can in fact show behavior that is as sophisticated as anything.

It’s been known for about a century that there exist computation universal systems capable of being “programmed” to do essentially any computation. But what the Principle of Computational Equivalence says is that sophisticated computation is not only possible—even for simple programs—but is something that happens generically and ubiquitously.

So what does this mean for our spacecraft? It means that what the spacecraft sees on Earth can be computationally no more sophisticated than what it sees on the planet with the swirling patterns. Yes, we consider there to be “intelligence” here on Earth. But what the Principle of Computational Equivalence tells us is that ultimately there’s nothing abstractly different going on from what’s going on in the swirling patterns.

So if we characterize what’s going on here on Earth as an example of “intelligence” we really should say that those swirling patterns are also “examples of intelligence”. And, yes, it doesn’t seem much like human intelligence. But at an abstract computational level it’s really operating like intelligence—but to us humans it’s “alien intelligence”.

There’s a common saying: “The weather has a mind of its own”. And what the Principle of Computational Equivalence tells us is that, yes, fluid dynamics in the atmosphere—and all the swirling patterns associated with it—are examples of computation that are just as sophisticated as those associated with human minds.

But, OK, so there’s a sense in which the weather “has a mind of its own”. But it’s definitely not a “human-like mind”. Yes, the weather does sophisticated computations. But there’s no obvious way to attribute to those computations the purposes and intentions and other typical features of how we describe what goes on in a human mind. So if indeed we’re going to talk about the weather as being an intelligence, for us humans we have to consider it an “alien intelligence”.

We started off talking about spacecraft going out into the cosmos to discover alien intelligence. But what the Principle Computational Equivalence is telling us is that actually there’s what we can think of as alien intelligence all around us. Yes, we humans have managed to get to the point where we do all sorts of sophisticated computations. But computations of just the same sophistication are being done in all sorts of systems that don’t have that whole human tower of biology and technology.

For a long time it’s been a mystery why we’ve never detected alien intelligence out there in the cosmos. But actually I think there’s no lack of “alien intelligence”; indeed it’s all around us. But the point is that it really is alien. At an abstract computational level it’s like our intelligence. But in its details it’s not aligned with our intelligence. Abstractly it’s intelligence, but it’s not human-like intelligence. It’s alien intelligence.

The Role of Science and Technology

OK, so we can think of lots of systems as being examples of “alien intelligence”. But how does that alien intelligence connect to our human intelligence? Sometimes it’s close enough that we humans can immediately “anthropomorphize” the system to “understand what it’s doing in human terms”. But often we need to put effort into “making a bridge”. And in fact we can view that as being what science and technology are ultimately trying to do.

Let’s say we’re looking at swirling patterns in a fluid. The fluid is doing what it does, in effect continually running a computation that generates its behavior. But how can we “align” that with what’s going on in our brains? That’s where science comes in. Because what science is trying to do is to extract some kind of “human-relatable narrative” from the actual behavior of a system out there in the world. Or in some sense it’s trying to provide a “channel” through which we can “communicate” with the “alien intelligence” that is embodied in what’s out there in the world.

So what about technology? Fundamentally technology is about trying to take what exists out there in the world, and apply it to achieve human purposes. We have a fluid. Now we use it to create hydraulic technology that achieves some practical human purpose. We can see the history of technology as being a progressive effort to identify things out there in the world (metal ore, photoelectricity, liquid crystals, …) that can be sampled and fashioned in such a way as to achieve certain purposes we want.

And insofar as we think of what’s out there in the world as being like alien intelligence, what technology is doing is finding ways to corral that intelligence into achieving human purposes. The truth is that in most of our technology today, we’re not letting that intelligence really do anything close to what it’s capable of. We’re keeping it tightly constrained to take only steps that we can readily understand and foresee. It’s a bit like having a horse with a harness that constrains it to just walk slowly in a straight line—even though without the harness the horse could gallop around and do all sorts of elaborate things, albeit things that we might not readily be able to understand or foresee.

So let’s come back to the spacecraft. It’s reached a planet. And it’s interacting with what’s there. Perhaps there’s some weird electrical storm going on. And, yes, we can think of that as an example of alien intelligence. But if the mission of the spacecraft is to discover technology then what it needs to do is to figure out whether there’s some way to interact with the electrical storm so as to achieve some human purpose.

The storm does what the storm does. But maybe by moving some piece of metal around in just the right way it’s possible to get the storm to charge a battery. Or, more elaborately, perhaps processes in the storm could be used like an analog computer, say to compute solutions to equations. And perhaps—having seen the storm on this planet—it’s even possible to “bottle it up” and replicate it, say in a piece of consumer electronics.

One way to describe what’s going on is just to say rather prosaically that we discovered a phenomenon on the planet, that we were able to use for technology. But more colorfully we could say that we encountered an alien intelligence, we found a way to communicate with it, and then we “brought back” technology from it.

The original startup pitch was about spacecraft getting technology by discovering alien intelligence out in the cosmos. But really the whole spacecraft thing is a distraction. Because actually—as we’ve discussed—there’s plenty we can describe as “alien intelligence” all around us, even right here on Earth. And the issue is in a sense just how to “communicate with it” and find ways to “harness it” for our technological purposes.

We’ve learned in the past century that we can use electrons in semiconductors as a way to build computers. But what about other physical processes? Maybe flowing fluids, for example. Can we use that “alien intelligence” to make a new kind of computer? In the end, the point is that any technology is about finding and harnessing “alien intelligence”. That’s basically just what technology is, and always has been.

The whole “alien intelligence” part of the story, though, is much more relevant when we’re thinking of technology that makes serious use of what we can identify as sophisticated computation. If we’re just using a system from nature for its physical mass, it doesn’t really feel as if we’re using its “intelligence”. But as soon as we try, for example, to base a general computer on it, it’s a quite different story.

In getting technology from the universe we’re basically picking out certain aspects of what exists and choosing to apply these for our purposes. In doing science it seems like we have “less choice” about what aspects of the universe we deal with. After all, we might imagine that science is trying to give us a way to understand anything that’s out there in the universe. But in reality it’s much more like technology. The “scientific narratives” that we understand—at least at a given time in history—are ones that we’re in a sense “primed for”. Yes, something like fluid turbulence might give us “in-your-face” exposure to something computationally sophisticated that’s far from what we normally talk about. But what science mostly concentrates on is creating narratives that are aligned with our existing scientific understanding and discussions—much as technology is set up to be about things that are aligned with our existing human purposes.

Extracting Technology from the Ruliad

One might imagine that—wherever it ultimately comes from—technology must at least always in the end be based on the laws of physics. But what’s emerging from our Physics Project is that actually the story is considerably more complicated than that.

It all begins with the ruliad: the object that represents the entangled limit of all possible computations. The ruliad is a unique, formally necessary object, that in a sense embodies all conceivable existence. And inevitably we are embedded within the ruliad, sampling certain aspects of it to form our perception of reality.

In principle there are all sorts of kinds of observers of the ruliad, with all sorts of kinds of perceptions of reality. But the key point that has emerged as a foundation of our Physics Project is that “observers like us” have certain general characteristics—specifically that we assume that we are persistent through time, and also that we are computationally bounded—and from these characteristics alone, we can abstractly deduce from the structure of the ruliad that we must “experience” core standard laws of known physics.

The ruliad in a sense contains all possible physicses. But it’s our particular kind of sampling of the ruliad that leads us to the particular laws of physics that we currently know. An “alien intelligence” might sample the ruliad quite differently, and thus in effect “experience” quite different laws of physics.

Somewhere underneath everything we can think of there being a giant hypergraph of individual atoms of existence—but with the means of perception observers like us have, we inevitably “coarse grain” to the point where, for example, we experience this as continuous space. Another kind of observer, with different characteristics, might, for example, not do that coarse graining, might never experience continuous space, and might have a completely different perception of how the universe works.

In some sense, therefore, physics is much more like technology than we might expect. There isn’t an “absolute physics”. There’s just the physics that we as observers extract from the ruliad. Much like there’s particular technology that we choose to build from the “raw material” that exists. Put another way, both physics and technology are ultimately things we “extract” from the ruliad, in effect by making certain choices.

How we “extract” physics seems, however, much more constrained. For example, we as humans have only certain particular senses through which we are biologically set up to experience the world. Yet we have the feeling that in technology we can in effect “construct whatever we want”—although inevitably “what we want” is also still at least influenced by how we are biologically set up.

We’re very used to the idea that over time technology progresses—as we invent more, and work out new ways to use our “raw material” to achieve human purposes. But physics as a science progresses too. And in a sense what’s happening there is that we’re expanding our character as observers to be able to perceive and experience more of “what’s going on”—ultimately in the ruliad.

Part of that expansion is actually a matter of technology. We’re building telescopes and microscopes and amplifiers that allow us to extend our raw human senses to be sensitive to more things. But there’s also another part of the expansion that is in effect intellectual: we’re developing new conceptual frameworks that allow us to “corral” things we see happening in the world into forms that “fit narratives” we’ve constructed.

And the important point here is that neither our technology nor our physics is fixed. They’re in a sense co-evolving—gradually allowing more and more of the ruliad to be pulled into our narratives and our purposes. Or, put another way, what we observe is gradually expanding to encompass more and more of the ruliad, and to be able to make use of more and more of it.

Reaching Out across Rulial Space

How are “different intelligences” manifest in the ruliad? We can imagine organizing the ruliad to be laid out in some form of rulial space. And from each point in rulial space one in effect gets a “different perspective” on the ruliad. And that’s at least the beginning of the story of how “different intelligences” exist and experience the ruliad.

It’s similar to what happens with physical space: from different places in physical space one gets a different perspective on the universe. In physical space we have a concept of motion: that observers like us can move from one place in space to another while in effect maintaining our coherence and integrity.

How does this work in rulial space? We can think of different points in rulial space as corresponding to different computations, with different rules. So rulial motion in effect corresponds to making a translation between one computation and another. At the outset, it’s not obvious this would even in principle be possible. But the Principle of Computational Equivalence implies that it ultimately will be. The computations at different points in rulial space will (almost always) be equivalent in their sophistication—and as is typical with universal computation—it’ll therefore in principle be possible to have an “interpretation process” that translates between them.

But the big question is whether this can be achieved in practice. Just how far can a particular observer translate in rulial space while maintaining their coherence and integrity?

The ruliad is a complex and (if sampled across slices in time) continually changing thing. But a critical feature is that there can be structures that have a certain persistence within it. In physical space these are things like particles (as well as black holes) that behave like “stable lumps of space”—or like stable lumps in certain projections of the ruliad. In rulial space there can presumably also be structures with a certain persistence: “particles” of rulial space. And these “particles” somehow correspond to features that “survive across different computational perspectives”—or in effect represent “robust concepts”.

When we talk about “different intelligences” a very familiar example is different human minds. And in a sense we can think of different human minds as being laid out in rulial space—with each mind being at a different rulial position, and thus having a different computational rule by which it operates, and a different “experience of the ruliad”.

So how can these minds “communicate”? Ultimately it is through “rulial motion”. But potentially the most robust form of rulial motion is through rulial particles—which we’ve identified above with the abstract idea of “robust concepts”. Put in a practical way: different (human) minds operate internally in different ways. But they can still “communicate” by exchanging something that in effect “survives translation” between one mind and another: rulial particles corresponding to robust concepts (say expressed in a language).

But, OK, we can imagine rulial space with lots of human minds laid out at different places, with ones that communicate more easily closer together. So what about “alien intelligences”? Well, each one is somewhere in rulial space. But they may be far away from where our human minds are.

We can imagine our rulial particles—or “robust concepts”—being able to reach a certain distance in rulial space. The human idea of “excitement” might for example be able to reach the place in rulial space where we’d find the minds of dogs. But what about the weather, for example? Well, as an alien intelligence, it’s presumably much further away in rulial space—and, anthropomorphize it as we might—it’s not clear what its notion of “excitement” would be.

It’s an often-asked question why—with our spacecraft and radio telescopes and everything else—we haven’t ever run across what we consider to be “naturally occurring” alien intelligences. In the past we might have imagined that the answer is that there just isn’t anything like “intelligence” (outside of us humans) to be found in any part of the universe that we can probe. But the Principle of Computational Equivalence says that’s fundamentally not true, and that in fact “abstract intelligence” is thoroughly ubiquitous among systems with all but the most obviously simple behavior.

So to “find” alien intelligence it’s not that we need a more powerful radio telescope (or a better spacecraft) that can reach further in physical space. Rather, the issue is to be able to reach far enough in rulial space. Or, put another way, even if we view the weather as “having a mind of its own”, the rulial distance between “its mind” and our human minds may be too great for us to be able to “understand” and “communicate with it”.

So what will it take for us to “bridge this rulial gap”? At some level it’s just about building the right science and technology. We can think of science as being about defining a way to “translate” from the computational rules by which some particular system operates to the computational way our human minds operate. Or, in terms of rulial space, finding a way to “move” from the rulial position of the system to the rulial position of our minds—and translating from the way a system works to a “human narrative” that represents it.

Centuries ago we might have just said “the planets do what they do”; maybe their motion in space is driven by an “alien intelligence” that we don’t understand. But then along came mathematical science and we were able to “translate” from the intrinsic computation done by the planets to a mathematical description that we internalized enough to consider it a human narrative that we understand.

In some sense at any given time in intellectual history our minds “reach out a certain distance in rulial space”. We’ve developed conceptual frameworks that allow us to maintain a coherent understanding of a certain range of things—with that range growing as we invent new frameworks. At one time our “domain of understanding”—or the region of rulial space that we could reach—didn’t encompass the behavior of electricity. But our “intellectual expansion” in rulial space eventually reached this, and the result is that we can now use electricity as “raw material” from which to construct technology.

One way we “expand our reach in rulial space” is in effect conceptual: by expanding what we understand. But another way is by being able to “sense” or “measure” more. When we invent radio—or, for that matter, gravitational wave detection—there are immediately new kinds of processes that we manage to “connect to human experience”. Or, put another way, there are more distant parts of the ruliad that we’re able to reach.

More prosaically, we can say that if we want to be able to use something for technology, we’d better be able to detect that it’s there, and we’d better be able to understand it well enough that we can see how it could align with our human purposes. We can think of the ruliad as being full of alien intelligences—with plenty of capabilities to “mine”. But to be able to actually mine something for our technological purposes we have to be able to reach it across rulial space; we have to be able to connect it to us.

So what does this mean for the original startup pitch? Yes, it’s a good idea to “mine alien intelligences” for technology. In fact, that’s basically where technology always comes from. But there’s no need to send out spacecraft, “discover” alien intelligence, and so on. There are “alien intelligences” all around us; the issue is just to reach them across rulial space, and be able to “communicate” with them. But what we’ve argued is that the process of progressively reaching out in rulial space is just the general process of progressively advancing science (and the technology on which it depends).

So, yes, by all means explore more of what’s out there in the world, with more, different kinds of sensors and measurements. Then try to “understand” what you see enough to be able to tell how to align it with human purposes, and make technology out of it. But there’s no pressing need for interstellar spacecraft in this picture. It’s just a matter of doing more science to expand our domain in the ruliad, and mine more of rulial space.

The Evolution of Purpose and the Colonization of Rulial Space

We can think of technology as being about setting up things that exist in the world (or ultimately in the ruliad) to achieve human purposes. And we’ve talked about how the advance of science and technology allows us to progressively reach further in rulial space to get “raw material” for our technology. But we’ve said that technology is intended to “achieve human purposes”. So what might those purposes ultimately be?

Our purposes have certainly evolved over the course of human history. In today’s world, we might view it as purposeful to walk on a treadmill, or to trade cryptocurrencies. But it would be challenging to explain the purpose of such things to someone from even a few hundred years ago.

In a sense, purposes evolve as we build new conceptual frameworks, and as we set up technology that allows us to do new things. More abstractly, we might say that purposes are also something defined by places in rulial space. So when we talk about the evolution of purposes, what we’re really asking is where in rulial space our history and development has led us, and will lead us in the future.

And certainly in the vastness of the whole ruliad, our existing human purposes occupy just an infinitesimally tiny part. Think, for example, of the natural world even as we are currently aware of it. The vast majority of things in it do not seem in any way aligned with our purposes—and we have not been able to mine them for technology. Historically, however, there’s been progressive expansion in the domain of our purposes. There was a time when we knew about magnetic rocks, but had no purpose for magnetism. But over the course of time, from compasses to actuators to memories, more and more human purposes have emerged that connect to the phenomenon of magnetism.

And in a sense we can view the whole core trajectory of human progress as being about the expansion of the region of rulial space—and the ruliad—that represents our purposes. So how will this evolve?

As I’ve discussed extensively before, there seem to be two central features that we as entities in the ruliad have. First, that we are computationally bounded. And second, that we believe we are persistent in time. Computational boundedness is essentially the statement that the region of rulial space that we occupy is limited. In some sense our minds can coherently span a certain region of rulial space, but it’s a bounded region.

What about persistence in time? It means that even though we are always being reconstructed out of different atoms of existence (and different atoms of space), we conflate things to the point where we experience a single continuous thread of existence.

Taken together, these features suggest a picture of us being a kind of “blob” that gradually moves around in rulial space. Does it matter that there isn’t just a single human mind? Well, yes. Without some kind of “observer” there’s no real way to even define what it means to have a “blob”. And in the end it’s a story of consistency of observers observing observers. But the result is that we can think of our whole collective “flotilla” of human purposes as being something localized that moves around in rulial space, expanding the region of the ruliad that it reaches.

But just how far can this go? Imagine that at some time in the distant future we have successfully explored—and “colonized”—much of rulial space. To do this we’d certainly have to have broken out of the particular constraints of our biological construction, and made use of “additional raw material” in the ruliad.

But what would it mean to be spread across a large swath of rulial space? Our very notion of existence seems to depend on localization in rulial space. The thing that we view as “us” is something particular and coherent. To be “bigger” in rulial space is to deny that particularity and coherence, and to become something generic that does not represent any kind of “specific entity that exists”.

In a sense, it’s a pyrrhic view of the ultimate limit of our technological and other evolution. As we progress, we gradually “mine” more and more of the ruliad, pulling it into the domain of technology and of our “human” (or post-human) purposes. But in doing so, we eventually transcend the very characteristics that we identify with existence. In other words, if we go too far with our expansion in the ruliad, we simply cease to exist, at least in the sense that we currently define existence.

Put another way, if we “absorb” more and more “alien intelligence” there’s eventually no longer any coherent “us”. Of course, the very notion of coherence is something we’re basically defining from our current human view of things. And no doubt there are other definitions that could be given. But they’re certainly far away from our current place in rulial space, and it’s not even clear they can be reached without some kind of “discontinuity of motion” that would in effect fundamentally break their connection to us as we are now.

Face to Face with Alien Intelligence, Out in Rulial Space

At a fundamental level, the ruliad is a purely computational object, that we can think of as being made of pure, abstract atoms of existence (or “emes”). When observers like us sample the ruliad we can attribute to it the characteristics that correspond to our perception of physical reality. And a notable feature of that sampling is that it supports the idea of pure motion in physical space. In other words, it allows for the possibility that structures can “maintain their perceived physical integrity” while being “re-formed” out of different atoms of space, which themselves are interpretations of the pure atoms of existence in the ruliad.

But as soon as we start thinking about any kind of serious motion in rulial (rather than physical) space it no longer makes sense to talk about anything like “maintaining physical integrity”, not least because in different places in rulial space the very notion of physics changes. But wherever we are in the ruliad we can still think about what’s going on as computation. We might have some way of observing or sampling the ruliad that gives us some perception of reality—like physics, or mathematics. But if we “atomize” things down to the lowest level, we’ll always find raw computation.

As “physical observers like us” we only have limited capabilities to probe or manipulate the raw ruliad and affect what we perceive as physical reality. We can move physical objects around, maintaining what we observe of their structure. In principle we could imagine deconstructing objects into individual atoms of existence, then recreating them “transporter style” somewhere else in physical space. But as of now, we don’t know how to do this, and most likely it’s not possible for observers like us—because it would require “outcomputing” computationally irreducible features of the structure of space down at the level of individual atoms of space, which is far from what computationally bounded observers like us can expect to do.

But what about raw computation, of the kind that ultimately makes up the ruliad? There the story is different. Because we’re no longer constrained by our character as physical observers, so we’re free to in effect “make up any computation we want”. To explore the physical universe we need physical motion or something like it. And at least for observers like us the only way to achieve this seems to be to progressively move structures across physical space. But to find out what can happen in the computational universe we can effectively just write down any rule (i.e. any program) that appears “anywhere in the ruliad”, and run it.

Of course, when we run a rule on a practical computer, it’s just an emulation of what’s happening in the raw ruliad. But it’s just an abstract rule—so although it will run astronomically slower, its ultimate behavior in our emulation will inevitably be identical to what it is when implemented in terms of individual atoms of existence in the “raw ruliad”.

In principle we could take the same approach in emulating the elements that make up our physical reality. But observers like us are so big relative to the raw elements of the ruliad that we can’t expect our emulations to be at a scale where we can faithfully reproduce what we perceive. (Needless to say, in practice we can still get good approximations, and this is a particularly fertile application of our Physics Project.)

But when we’re dealing with “raw computation” down at the lowest level of the raw ruliad, we can expect to faithfully emulate it. And so it is that we can just pick a cellular automaton or a Turing machine or some other kind of computational system—that in effect comes from anywhere in the ruliad—and emulate it to find out what it does. There’s no “object we have to move” to be able to “look at that part of the ruliad”. We’re emulating things down at the level of individual atoms of existence, and seeing what happens.

We can think about our computational experiments as letting us “jump” to find out what it’s like anywhere in the ruliad. And as we “suddenly materialize” somewhere in the ruliad it’s as if we’re immediately “face to face” with whatever “alien intelligence” there is at that place in the ruliad.

But what can “observers like us” expect to make of that alien intelligence? Well, to be able “communicate” or even “relate” we somehow have to be able to “bridge the gap in rulial space”. And since we just “jumped to a place in rulial space” we don’t immediately have any “progressive path” that “incrementally” takes us from our familiar position in rulial space to wherever the alien intelligence is.

But what does that feel like in practice? The whole idea of ruliology is just to go anywhere we want in the computational universe or in the ruliad, and see what happens when we run the rules we find there. And it’s indeed routine to find that what they do seems quite “alien”. Still, they often have certain essential features that for example remind us of the natural world as we observe it. But our standard methods of science (and mathematics)—developed on the basis of being “observers like we are today”—don’t readily allow us to “understand” the behavior of these systems chosen in the course of doing ruliology. To us they usually just seem to be “showing computational irreducibility”, and behaving in ways that we can effectively get no handle on.

But still, we can in a sense view these programs “out there in the computational universe” (and in effect strewn around the ruliad) as showing us what’s possible. They’re like alien intelligences that we know exist, but that we don’t yet understand, and don’t yet know how to harness or relate to. We can see them as some kind of beacons of possible technology of the future—of things that “exist in the ruliad”, but that we haven’t yet been able to connect to human purposes.

But so how might we make this connection? Well, as it happens, I’ve devoted much of my life to what can be viewed as the construction of a systematic bridge between what’s “computationally possible” and what we humans think of as important. For that’s the story of what I call computational language—and indeed of the whole intellectual structure that is the Wolfram Language.

There’s infinite potential content in the ruliad. But one can view the goal of the Wolfram Language as being to represent—in a way that’s optimized for us humans to understand—those parts that we humans consider important. The language lets us use the concepts of computation not only to crystallize our existing thinking, but also to expand what we can think about, in effect letting us reach out further in rulial space. Computational language is the general way that we “tame the ruliad”—extend the frontier of “human colonization” in the ruliad, and in the end “mine” more and more of the ruliad for “useful technology”.

Just in terms of its practical place in the world today I’ve often said that the Wolfram Language is like an “artifact from the future”. But now we see a deep sense in which this is true. The raw ruliad is just “out there”, with “infinite potential”, but as something whose fundamental character has nothing to do with us humans. But what computational language is about is delivering what one can think of as the ultimate “meta-artifact”: something that progressively turns the raw ruliad into “human-recognizable technology”.

Much of this progress involves the specific, systematic design of the Wolfram Language. But there are also forays that in effect jump further out into rulial space. For example, we’ve often enumerated large collections of simple programs, identifying ones that satisfy a certain criterion. And sometimes that feels a lot like “leveraging alien intelligence” without “understanding” it. The rule 30 cellular automaton, for example, is a good pseudorandom generator, even though we don’t really “understand” even fairly basic things about it.

And, yes, computational language is what we need to concretely “state a criterion”, in effect expressing what we’re thinking about in computational terms—that we can use, for example, to let us explicitly search the ruliad for an “alien intelligence” that does what we want.

What does it look like out in the “raw ruliad”? It’s easy to start just looking at simple programs, say picked at random. And, yes, they have all sorts of elaborate behavior:

&#10005

But what is this behavior “achieving”? Yes, it’s following the particular underlying rules that have been given. But we don’t have any immediate way to connect it to “human purposes”. And in general we can expect that to make that connection what’s needed is for those purposes themselves to “expand”.

Maybe at some moment we call what’s produced “art”, and assign it some “aesthetic purpose”. Maybe at some point we see that it satisfies some engineering purpose that we’ve just realized we should care about. But in general, computational language is the way we can make the connection between “raw computational processes” out there in the ruliad, and our patterns of thinking about things. It’s the ultimate way for us to “communicate with alien intelligence”.

The Launch of a Rulial Space Program

We began with the far-out startup pitch of sending spacecraft to discover alien intelligence and bring its technology back to Earth. But what we’ve realized is that actually no spacecraft—of the ordinary kind—are needed. There’s “alien intelligence” to be found everywhere; you don’t have to travel to interstellar space to find it. But the challenge is to connect the “alien intelligence” to human purposes, and extract from it what we consider “useful technology”. Or, put another way, the issue is not about traversing physical space, but rather about traversing rulial space.

With our spacecraft we humans have so far reached about a 20-trillionth of the way across the physical universe. But no doubt we’ve reached a far smaller fraction of the way across the ruliad. As our science, knowledge and technology increase, we gradually reach further into rulial space. But whether it’s our failure to communicate with cetaceans or our inability to make computers out of, say, fluids, it’s clear that by many measures the distance we’ve gone so far is not so large.

In a sense the startup idea of “harnessing alien intelligence” is the meta-idea of all technology—that in our terms we can state as being to connect what’s “computationally possible” in the ruliad with purposes we humans want to achieve. And I’ve argued that the ultimate meta-technology for doing this is not spacecraft but computational language. Because computational language is what we need to make a bridge between what we care about, and “raw computation” out in the ruliad.

It’s difficult to send physical spacecraft out into interstellar space. But it’s actually a lot easier to probe the much richer possibilities of the ruliad—because in a sense it’s straightforward to put a “rulial spacecraft” anywhere. We just have to pick a rule (or program), then see what the “world” it generates is. But the challenge is then in a sense one of interpretation. What is happening in that world? Can we relate it to things we care about?

At the outset, all we’re likely to see at some “random place” in the ruliad is rampant computational irreducibility. But it’s a fundamental fact that wherever there’s computational irreducibility, there must also be slices of computational reducibility to be found. In the ordinary physical universe that we experience, those are basically our perceived laws of physics. But even in a random sample of the ruliad we can expect there’ll be computational reducibility to be found. It’ll typically be “alien stuff”, though. It might have the character of science, but it won’t be like our existing science. And most likely it won’t align with anything we currently think we care about.

But that is the great challenge and promise of mounting a “rulial space program”. To be confronted not with what we might recognize as “new life and new civilizations”, but with things for which we have no description and no current way of thinking. Perhaps we might view it merely as humbling to encounter such things, and to realize how small a part of the ruliad we yet understand. But we can also view it as a beacon of where we could go. And we can view a whole “rulial space program” as a way of systematizing the ultimate project of exploring all formally possible processes. Or we could think about it not just as defining a single “startup opportunity”—but rather as defining the “meta-opportunity” of all possible technology startups….