Formal Structure

⇒ The formal structure of Multicomputation

In the previous section, we discussed how the multicomputational paradigm plays out in the particular case of fundamental physics. And in many ways, physics is probably a fairly typical application of the paradigm. But there are some special features it has that add complication, though also add concreteness. So what are the ultimate foundations of the multicomputational paradigm? At its core, I think it’s fair to say that the paradigm is about events and their relationships—where the events are defined by some kind of rules.

What happens in an Event? It’s a bit like the application of a function. It takes some set of “expressions” or “tokens” as input, and returns some other set as output.

In a simple ordinary computational system there might just be one input and one output expression for each event, as in x ⟼ f[x], leading to a trivial graph for the sequence of states reached in the evolution of the system: […]

But now let’s imagine that there are two expressions generated by each event: x ⟼ {f[x], g[x]}. Then the evolution of the system can instead be represented by the tree: […]

But what starts making a nontrivial multiway graph is when some states that are generated in different ways end up Being the Same, so that they get merged in the graph. As an example, consider the rule […]

The multiway graph produced in this case is […]

Both the results we’ve just got are subgraphs of the full multiway graph. But they both have the feature that they effectively just yield a single sequence of states for the system. In the first case this is obvious. In the second case there are little “temporary branchings” but they always merge back into a single state. And the reason for this is that with the evaluation strategy we’ve used, we only ever get spacelike-separated events, so there are no “true multiway branches”, as would be generated by branchlike-separated events. But even though ultimately there’s just a “single branch of history” there’s a “shadow” of the presence of other branches visible in the nontrivial causal graph that shows causal relationships between updating events: […]

So what about our models of physics? In exploring them it’s often convenient not to track the whole multiway system but instead just to look at the results from a particular “evaluation strategy”. In a hypergraph there’s no obvious “scan order”, but we still often use a strategy that—like our second string strategy above—attempts to “do whatever can be done in parallel”. Inevitably, though, there’s a certain arbitrariness to this. But it turns out there’s a more “principled” way to set things up. The basic idea is not to think about complete states (like strings or hypergraphs) but instead just to think separately about the “tokens” that will be used as inputs and outputs in events. And—giving yet more evidence that even though hypergraphs may be hard for us humans to handle, there’s great naturalness to them—it’s considerably easier to do this for hypergraphs than for strings. And the basic reason is that in a hypergraph each token automatically comes “appropriately labeled”. The relevant tokens for hypergraphs are hyperedges. And in a rule like […]

we see that two “hyperedge tokens” are used as input, and four “hyperedge tokens” are generated as output. And the point is that when we have a hypergraph like […]

[…] we can just think of this as an unordered “sea” (or multiset) of hyperedges, where each event will just pick up some pair of hyperedges that match the pattern {{x, y}, {y, z}}. But what does it mean to “match the pattern”? x, y, z can each correspond to any node of the hypergraph (i.e. for our model of physics, any atom of space). But the key constraint is that the two instances of y must refer to the same node. If we tried to do the same thing for strings, it’d be considerably more difficult. Because then the relevant tokens would be individual characters in the string. But whereas in a hypergraph every token is a hyperedge that can be identified from the uniquely named nodes it contains, every A or every B in a string is usually thought of as just being the same—giving us no immediate way to identify distinct tokens in our system. But assuming we have a way to identify distinct tokens, we can consider representing the evolution of our system just in terms of events applied to tokens (or what we can call a “token-event graph”). This is going to get a bit complicated. But here’s an example of how it works for the hypergraph system we’ve just shown. Each blue node is a token (i.e. a hyperedge) and each yellow node is an event: […]

What’s going on here? At each step shown, there’s a token (i.e. blue node) for every hyperedge generated at that step. Let’s compare with the overall sequence of hypergraphs: […]

The initial state contains two hyperedges, so there are two tokens at the top of the token-event graph. Both these hyperedges are “consumed” by the event associated with applying the rule—and out of that event come four new hyperedges, represented by the four tokens on the next step. Let’s look in a little more detail at what’s happening. Here is the beginning of the token-event graph, annotated with the actual hyperedges represented by each token (the numbers in the hyperedges are the “IDs” assigned to the “atoms of space” they involve): […]

At the first step our rule {{x,y},{y,z}} → {{w,y},{y,z},{z,w},{x,w}} consumes the hyperedges {0,0} and {0,0} and generates four new hyperedges. (Note that the {0,0} on step 2 is considered a “new hyperedge”, even though it happens to have the same content as both hyperedges on step 1; more about this later.) At the second step, the rule consumes {1,0} and {0,0}. And at the third step, there are two invocations of the rule (i.e. two events), each consuming two hyperedges, and generating four new ones. And looking at this one might ask “Why did the second event consume {1,0} and {0,0} rather than, say, {1,0} and one of the {0,1} tokens?” Well, the answer is that the token-event graph we’re showing is just for a specific possible history, obtained with a particular “evaluation strategy”—and this is what that strategy picked to do. But it’s possible to extend our token-event graph to show not just what can happen for a particular history, but for all possible histories. In effect what we’re getting is a finer-grained version of our multiway graph, where now the (blue) nodes are not whole states (i.e. hypergraphs) but instead just individual tokens (i.e. hyperedges) from inside those states.

Here’s the result for a single step:

There are two possible events because the two initial hyperedges given here can in effect be consumed in two different orders. Continuing even one more step things rapidly get significantly more complicated: […]

Let’s compare this with our ordinary multiway graph (including events) for the same system: […]

Why is this so much simpler? First, it’s because we’ve collected the individual tokens (i.e. hyperedges) into complete states (i.e. hypergraphs)—“knitting them together” by seeing which atoms they have in common. But we’re doing something else as well: even if hypergraphs are generated in different ways, we’re conflating them whenever they’re “the same”. And for hypergraphs our definition of “being the same” page is that they’re isomorphic, in the sense that we can transform them into each other just by permuting node labels. Note that if we don’t conflate isomorphic hypergraphs the multiway graph we get is […]

[…] which corresponds much more obviously to the token-event graph above. When we think about multicomputational systems in general, the conflation of “identical” (say by isomorphism) states is in a sense the “lowest-level act” of an observer. The “true underlying system” might in some sense “actually” be generating lots of separate, identical states. But if the observer can’t tell them apart then we might as well say they’re all “the same state”. (Of course, when there are different numbers of paths that lead to different states, this can affect the weightings of these different states—and indeed in our model of physics this is where the different magnitudes of quantum amplitudes for different states come from.) It seems natural and obvious to conflate hypergraphs if they’re isomorphic. But actual observers (say humans observing the physical universe) typically conflate much, much more than that. And indeed when we say that we’re operating in some particular reference frame we’re basically defining potentially huge collections of states to conflate. But there’s actually also a much lower level at which we can do conflation. In the token-event graphs that we’ve looked at so far, every token generated by every event is shown as a separate node. But—as the labeled versions of these graphs make clear—many of these tokens are actually identically the same, in the sense that they’re just direct copies created by our way of computing (and rendering) the token-event graph. So what about conflating all of these—or in effect “deduplicating” tokens so that we have just one unique shared representation of every token, regardless of how many times or where it appears in the original graph? Here’s the result after doing this for the 2-step version of the token-event graph above: […]

This deduplicated-token-event graph in essence records every “combinatorially possible” “distinct event” that yields a “transition” between distinct tokens. But while sharing the representation of identical tokens makes the graph much simpler, the graph now no longer has a definite notion of “progress in time”: there are edges “going both up and down”, sometimes even forming loops (i.e. “closed timelike curves”). So how can this graph represent the actual evolution of the original system with a particular evaluation strategy (or, equivalently, as “viewed in a particular reference frame”)? Basically what we need are some kind of “markers” that move around the graph from “step to step” to indicate which tokens are “reached” at each step. And doing this, this is what we get for the “standard evaluation strategy” above: […]

In a sense a deduplicated token-event graph is the ultimate minimal invariant representation of a multicomputational system. (Note that in physics and elsewhere the graph is typically infinite.) But any particular observer will effectively make some kind of sampling of this graph. And in working out this sampling we’re going to encounter issues about knitting together states and reference frames—that are ultimately equivalent to what we saw before from our earlier perspective on multiway systems. (Note that if we had a deduplicated token-event graph with markers that is finite then this would basically be a Petri net, with decidable reachability results, etc. But in most relevant cases, our graphs won’t be finite.) So although token-event graphs—even in deduplicated form—don’t ultimately avoid the complexities of other representations of multicomputational systems, they do make some things easier to discuss. For example, in a token-event graph there’s a straightforward way to read off whether two events are branchlike or spacelike separated. Consider the “all histories” token-event graph we had before: […]

To figure out the type of separation between events, we just need to look at their first common ancestor. If it’s a token, that means the events are branchlike separated (because there must have been some “ambiguity” in how the token was transformed). But if the common ancestor is an event, that means the events we’re looking at are spacelike separated. So, for example, events 1 and 2 here are branchlike separated, as are 4 and 5. But events 4 and 9 are spacelike separated. Note that if instead of looking at an “all histories” token-event graph, we restrict to a single history then there will only be spacelike- (and timelike-) separated events: […]

A token-event graph is in a sense a lowest-level representation of a multicomputational system. But when an observer tries to “see what’s going on” in the system, they inevitably conflate things together, effectively perceiving only certain equivalence classes of the lowest-level elements. Thus, for example, an observer might tend to “knit together” tokens into states, and pick out particular histories or particular sequences of time slices—corresponding to using what we can call a certain “reference frame”. (In mathematical terms, we can think of particular histories as like fibrations, and sequences of time slices as like foliations. ) And in studying multicomputational systems of different types a key question is what kinds of reference frames are “reasonable” based on some general model for the observer. And one almost inevitable constraint is that it should only require bounded computational effort to construct the reference frame. Our Physics Project then suggests that in appropriate large-scale limits specific structures like general relativity and quantum mechanics should then emerge. And it seems likely that this is a general and very powerful result that’s essentially inexorably true about the limiting behavior of any multicomputational system. But if so, the result represents an elaborate—and unprecedented—interweaving of fundamentally computational and fundamentally mathematical concepts. Maybe it’ll be possible to use a generalization of category theory as a bridge. But it’s going to involve not only discussing ways in which operations can be applied and composed, but also what the computational costs and constraints are. And in the end computational concepts like computational reducibility are going to have to be related to mathematical concepts like continuity—I suspect shedding important new light all around. Before closing our discussion of the formalism of multicomputation there’s something perhaps still more abstract to discuss—that we can call “rulial multicomputation”. In ordinary multicomputation we’re interested in seeing what happens when we follow certain rules in all possible ways. But in rulial multicomputation we go a step further, and also ask about following all possible rules. One might think that following all possible rules would just “make every possible thing happen”—so there wouldn’t be much to say. But the crucial point is that in a (rulial) multiway system, different rules can lead to equivalent results, yielding a whole elaborately entangled structure of possible states and events. But at the level of the token-event formalism we’ve discussed above, rulial multicomputation in some sense just “makes events diverse”, and more like tokens. For in a rulial multiway system, there are lots of different kinds of events (representing different rules)—much as there are different kinds of tokens (containing, for example, different underlying elements or atoms). And if we look at different events in a rulial multiway system, there is now another possible form of separation between them: in addition to being timelike, spacelike or branchlike separated, the events can also be rulelike separated (i.e. be based on different rules). And once again we can ask about an observer “parsing” the (rulial) multiway system, and defining a reference frame that can, for example, treat events in a single “rulelike hypersurface” as equivalent. I’ve discussed elsewhere the rather remarkable implications of rulial multiway systems for our understanding of the physical (and mathematical) universe, and its fundamental formal necessity. But here the main point to make is that the presence of many possible rules doesn’t fundamentally affect the formalism for multicomputational systems; it just requires the observer to define yet more equivalences to reduce the “raw multiway behavior” to something computationally simple enough to parse. And although one might have thought that adding the concept of multiple rules would just make everything more complicated, I won’t be surprised if in the end the greater “separation” between “raw behavior” and what the observer can perceive will actually make it easier to derive robust general conclusions about overall behavior at the level of the observer.

⇒ Physicalized Concepts in Multicomputation