Multicomputation with Numbers: The Case of Simple Multiway Systems

Stephen Wolfram

Multicomputation with Numbers: The Case of Simple Multiway Systems

A Minimal Example of Multicomputation

Multicomputation is an important new paradigm, but one that can be quite difficult to understand. Here my goal is to discuss a minimal example: multiway systems based on numbers. Many general multicomputational phenomena will show up here in simple forms (though others will not). And the involvement of numbers will often allow us to make immediate use of traditional mathematical methods.

A multiway system can be described as taking each of its states and repeatedly replacing it according to some rule or rules with a collection of states, merging any states produced that are identical. In our Physics Project, the states are combinations of relations between elements, represented by hypergraphs. We’ve also often considered string substitution systems, in which the states are strings of characters. But here I’ll consider the case in which the states are numbers, and for now just single integers.

And in this case multiway systems can be represented in a particularly simple way, with each state s just being repeatedly replaced according to:

s(s), … , }

For a “binary branching” case the update rule is

&#10005


and one can represent the evolution of the system by the multiway graph which begins:

&#10005


and continues (indicating by red and by blue):

&#10005


With arbitrary “symbolic” this (“free multiway system”) tree is the only structure one can get. But things can get much less trivial when there are forms for , that “evaluate” in some way, because then there can be identities that make branches merge. And indeed most of what we’ll be discussing here is associated with this phenomenon and with the “entanglements” between states to which it leads.

It’s worth noting that the specific setup we’re using here avoids quite a lot of the structural complexity that can exist in multicomputational systems. In the general case, states can contain multiple “tokens”, and updates can also “consume” multiple tokens. In our case here, each state just contains one token—which is a single number—and this is what is “consumed” at each step. (In our Physics Project, a state corresponds to a hyperedge which contains many hyperedge tokens, and the update rule typically consumes multiple hyperedges. In a string substitution system, a state is a character string which contains many character tokens, and the update typically consumes multiple—in this case, adjacent—character tokens.)

With the setup we’re using here there’s one input but multiple outputs (2 in the example above) each time the update rule is applied (with the inputs and outputs each being individual numbers). It’s also perfectly possible to consider cases in which there are multiple inputs as well as multiple outputs. But here we’ll restrict ourselves to the “one-to-many” (“traditional multiway”) case. And it’s notable that this case is exceptionally easy to describe in the Wolfram Language:

&#10005


Multiway Systems Based on Addition

As our first example, let’s consider multiway systems whose rules just involve addition.

The trivial (“one-input, one-output”) rule

&#10005


gives a multiway graph corresponding to a “one-way number line”:

&#10005


The rule

&#10005


gives a “two-way number line”:

&#10005


But even

&#10005


gives a slightly more complicated multiway graph:

&#10005


What’s going on here? Basically each triangle represents an identity. For example, starting from 1, applying twice gives 3, which is the same result as applying once. Or, writing the rule in the form

&#10005


the triangles are all the result of the fact that in this case

&#10005


For the “number line” rule, it’s obvious that we’ll eventually visit every integer—and the +1, +2 rule also visits every integer.

Consider now instead of +1 and +2 the case of +2 and +3:

&#10005


After a few steps this gives:

&#10005


Continuing a little longer gives:

&#10005


It’s a little difficult to see what’s going on here. It helps to show which edges correspond to +2 and +3:

&#10005


We’ll return to this a little later, but once again we can see that there are cycles in this graph, corresponding to simple “commutativity identities”, such as

&#10005


and

&#10005


as well as “LCM identities” such as

&#10005


(Note that in this case, all integers above 1 are eventually generated.)

Let’s look now at a case with slightly larger integers:

&#10005


After 6 steps one gets a simple grid

&#10005


essentially made up of “commutativity identities”. But continuing a little longer one sees that it begins to “wrap around”

&#10005


eventually forming a kind of “tube” with a spiral grid on the outside:

&#10005


The “grid” is defined by “commutativity identities”. But the reason it’s a “closed tube” is that there are also “LCM identities”. To understand this, unravel everything into a grid with +4 and +7 directions—then draw lines between the duplicated numbers:

&#10005


The “tube” is formed by rolling the grid up in such a way as to merge these numbers. But now if we assume that the multiway graph is laid out (in 3D) so that each graph edge has unit length, application of Pythagoras’s theorem in the picture above shows that the effective circumference of the tube is .

In another representation, we can unravel the tube by plotting numbers at {x, y} according to their decomposition in the form :

&#10005


(From this representation we can see that every value of n can be reached so long as .)

For the rule

&#10005


the multiway graph forms a tube of circumference which can be visualized in 3D as:

&#10005


And what’s notable here is that even though we’re just following a simple discrete arithmetic process, we’re somehow “inevitably getting geometry” out of it. It’s a tiny, toy example of a much more general and powerful phenomenon that seems to be ubiquitous in multicomputational systems—and that in our models of physics is basically what leads to the emergence of things like the limiting continuum structure of space.

We’ve seen a few specific example of “multiway addition systems”. What about the more general case?

For

&#10005


a “tube” is generated with circumference

where = {a, b}/GCD[a, b]

After enough steps, all integers of the form k GCD[a, b] will eventually be produced—which means that all integers are produced if a and b are relatively prime. There’s always a threshold, however, given by FrobeniusNumber[{a, b}]—which for a and b relatively prime is just a bab.

By the way, a particular number n—if it’s going to be generated at all—will first be generated at step

&#10005


(Note that the fact that the multiway graph approximates a finite-radius tube is a consequence of the commensurability of any integers a and b. If we had a rule like , we’d get an infinite 2D grid.)

For

&#10005


a tube is again formed, with a circumference effectively determined by the smaller pair (after GCD reduction) of a, b and c. And if GCD[a, b, c] = 1, all numbers above FrobeniusNumber[{a, b, c}] will eventually be generated.

Pure Multiplication

One of the simplest cases of multiway systems are those based on pure multiplication. An example is (now starting from 1 rather than 0):

&#10005


&#10005


In general, for

&#10005


we’ll get a simple 2D grid whenever a and b aren’t both powers of the same number. With d elements in the rule we’ll get a d-dimensional grid. For example,

&#10005


gives a 3D grid:

&#10005


If the multipliers in the rule are all powers of the same number, the multiway graph degenerates to some kind of ladder. In the case

&#10005


this is just:

&#10005


while for

&#10005


it is

&#10005


and in general for

&#10005


it is a “width-m” ladder graph.

Multiplication and Addition: n ⟼ {a n, n + b}

Let’s look now at combining multiplication and addition—to form what we might call affine multiway systems. As a first example, consider the case (which I actually already mentioned in A New Kind of Science):

&#10005


&#10005


Considering the simplicity of the rule by which it was generated, this result looks surprisingly complex. One immediate result is that after t steps, the total number of distinct numbers reached is Fibonacci[t – 1], which increases exponentially like . Eventually the ensures that every integer is generated. But the often “jumps ahead”, and since the maximum number generated at step t is the “average density” of numbers falls exponentially like .

Continuing the evolution further and using a different rendering we get the very “geometrical” (planar) structure

&#10005


What can we say about this structure? Apart from the first few steps (rendered at the center), it consists of a spiral of pentagons. Each pentagon (except the one at the center) has the form

&#10005


reflecting the relation

&#10005


Going out from the center, each successive layer in the spiral has twice the number of pentagons, with each pentagon at a given layer “spawning” two new pentagons at the next layer.

Removing “incomplete pentagons” this can be rendered as:

&#10005


What about other rules of the general form:

&#10005


Here are the corresponding (“complete polygon”) results for through 5:

&#10005


The multiway graphs in these cases correspond to spirals of ()-gons defined by the identity

&#10005


or equivalently

&#10005


At successive layers in the spiral, the number of ()-gons increases like .

Eventually the evolution of the system generates all possible integers, but at step t the number of distinct integers obtained so far is given by the generalized Fibonacci series obtained from

&#10005


which for large t is

where is the k-nacci generalized golden ratio, which approaches for large k.

If we consider

&#10005


it turns out that one gets the same basic structure (with ()-gons) for as for . For example, with

&#10005


one gets:

&#10005


The Rule n ⟼ {2n + 1, 3n + 1}

For the rule

&#10005


there are at first no equivalences that cause merging in the multiway graph:

&#10005


But after 5 steps we get

&#10005


where now we see that 15 and 31 are connected “across branches”.

After 10 steps this becomes:

&#10005


At a visual level this seems to consist of two basic components. First, a collection of loops, and second a collection of tree-like “loose ends”. Keeping only complete loops and going a few more steps we get:

&#10005


Unlike in previous cases, the “loops” (AKA “polygons”) are not of constant size. Here are the first few that occur (note these loops “overlap” in the sense that several “start the same way”):

&#10005


As before, each of these loops in effect corresponds to an identity about compositions of functions—though now it matters what these compositions are applied to. So, for example, the 4th loop above corresponds to (where k stands for the function ):

&#10005


In explicit form this becomes:

&#10005


where both sides evaluate to the same number, in this case 26815.

Much as in the Physics Project, we can think of each “loop” as beginning with the creation of a “branch pair”, and ending with the merger of the different paths from each member of the pair. In a later section we’ll discuss the question of whether every branch pair always in the end re-merges. But for now we can just enumerate mergers—and we find that the first few occur at:

&#10005


(Note that a merger can never involve more than two branches, since any given number has at most one “pre-image” under and one under .)

Here is a plot of the positions of the mergers—together with a quadratic fit (indicated by the dotted line):

&#10005


(As we’ll discuss later, the numbers at which these mergers occur are for example always of the form .)

Taking second differences indicates a certain apparent randomness:

&#10005


What can we say about the overall structure of the multiway graph? One basic question is what numbers ever even occur in the evolution of the system. Here are the first few, for evolution starting from 0:

&#10005


And here are successive differences

&#10005


Dividing successive m by the number gives a progressive estimate of the density of numbers:

&#10005


On a log-log scale this becomes

&#10005


showing a rough fit to —and suggesting an asymptotic density of 0.

Note, by the way, that while the maximum gap grows on average linearly (roughly like 0.17 m)

&#10005


the distance between gaps of size 1 shows evidence of remaining bounded:

&#10005


(A related result from the 1970s states that the original sequence contains infinite-length arithmetic progressions—implying the presence of infinite runs of numbers whose differences are constant.)

The More General “Affine” Case: n ⟼ {a n + b, c n + d}

Not every rule of the form

&#10005


leads to a complex multiway graph. For example

&#10005


just gives a pure binary tree since 2n just adds a 1 at the beginning of the binary digit sequence of n, while adds one at the end:

&#10005


Meanwhile

&#10005


gives a simple grid

&#10005


where at level t the numbers that appear are simply

&#10005


and the pattern of use of the two cases in the rule makes it clear why the grid structure occurs.

Here are the behaviors of all inequivalent nontrivial rules of the form

&#10005


with constants up to 3:

&#10005


“Ribbons” are seen only when . “Simple webs” are seen when . “Simple grids” are seen whenever the two cases in the rule commute, i.e.

&#10005


which occurs whenever

&#10005


“Simple trees” are seen whenever

&#10005


In other cases there seems to be irregular merging, as in the case above. And keeping only nontrivial inequivalent cases these are the results after removing loose ends:

&#10005


Note that adding another element in the rule can make things significantly more complicated. An example is:

&#10005


After 8 steps this gives

&#10005


or in another rendering:

&#10005


After a few more steps, with “loose ends” removed, one gets the still-rather-unilluminating result (though one that we will discuss further in the next section):

&#10005


The Phenomenon of Confluence

Will every branching of paths in the multiway graph eventually merge again? If they do, then the system is confluent (which in this case is equivalent to saying that it’s causal invariant—an important property in our Physics Project).

It turns out that all rules of the following forms are confluent:

&#10005


&#10005


&#10005


&#10005


But among rules of the form

&#10005


confluence depends on the values of a, b, c and d. When multiway graphs are “simple webs” or “simple grids” there is obvious confluence. And when the graphs are simple trees, there is obviously not confluence.

But what about a case like the rule we discussed above:

&#10005


We plotted above the “positions” of mergers that occur. But are there “enough” mergers to “rejoin” all branchings?

Here are the first few branchings that occur:

&#10005


For the pair 3, 4 one can reach a “merged” end state on the following paths:

&#10005


which are embedded in the whole multiway graph (without loose ends) as:

&#10005


For the pair 9, 13 both eventually reach 177151, but 9 takes 13 steps to do so:

&#10005


Here’s a summary of what we know about what happens with the first few branchings:

&#10005


So what about the total number of branchings and mergings? This is what happens for the first several steps:

&#10005


The number of branchings at step t approximates

&#10005


while the number of mergings seems to grow systematically more slowly, perhaps like 1.:

&#10005


And based on this it seems plausible that the system is not in the end confluent. But how might we show this? And what is the best way to figure out if any particular branch pair (say 21, 31) will ever merge?

One way to look for mergings is just to evolve the multiway graph from each member of the pair, and check if they overlap. But as we can see even for the pair {3, 4} this effectively involves “treeing out” an exponential number of cases:

&#10005


&#10005


Is there a way to do this more efficiently, or in effect to prune the trees? A notable feature of the original rule is that the numbers it generates always increase at each step. So one thing to do is just to discard all elements at a particular step in one graph that cannot reach the “minimum frontier” in the other graph. But on its own, this leads to only very minor reduction in the size of graph that has to be considered.

To find what is potentially a much more effective “optimization” let’s look at some examples of mergings:

&#10005


It’s clear that the final step has to consist of one application of and one of (i.e. one red edge and one blue edge). But these examples suggest that there are also further regularities.

At the merging point it must be true that

&#10005


for some integers u and v. But for this to be true, the merged value (i.e. or ) must for example be equal to 1 mod 2, 3 and 6.

Using the structure one level back we also have:

&#10005


or

&#10005


implying that the merged value must be 3 mod 4, 7 mod 12, 13 mod 18 and 36 mod 31. Additional constraints from going even further back imply in the end that the merged value must have the following pattern of residues:

&#10005


But now let’s consider the whole system modulo k. Then there are just k possible values, and the multiway graph must be finite. For example, for we get:

&#10005


Dropping the “transient parts” leaves just:

&#10005


These graphs can be thought of as reductions of the multiway graph (and, conversely, the multiway graph is a covering of them). The graphs can also be thought of as finite automata that define regular languages whose elements are the “2” and “3” transformations that appear on the edges. Any sequence of “2” and “3” transformations that can occur in the multiway graph must then correspond to a valid word in this regular language. But what we have seen is that for certain values of k, mergers in the multiway graph always occur at particular (“acceptor”) states in the finite automata.

In the case , every merger occurs at the 7 state. But by tracing possible paths in the finite automaton we now can read off what sequences of transformations can lead to a merger:

&#10005


And what’s notable is that only a certain fraction of all possible sequences of length m can occur; asymptotically, about 28%.

The most stringent analogous constraints come from the graph:

&#10005


And we see that even for sequences of length 3 fewer are allowed than from the graph:

&#10005


Asymptotically the number of allowed sequences is about 3% of the possible. And so the conclusion is that if one wants to find mergings in the multiway graph it’s not necessary to tree out all possible sequences of transformations; one only needs at most the 30× smaller number of sequences “accepted by the mod-144 finite automaton”. It’s possible to do a little better than this, by looking not just at sequences allowed by the finite automaton for a particular k, but at finite automata for a collection of values of k (say as in the table above).

But while these techniques deliver significant practical speedups they do not seem to significantly alter the asymptotic resources needed. So what will it take to determine whether the pair {21, 31} ever merges?

I don’t know. And for example I don’t know any way to find an upper bound on the number of steps after which we’d be able to say “if it hasn’t merged yet, it never will”. I’m sure that if we look at different branch pairs, there will be tricks for particular cases. But I suspect that the general problem of determining merging will show computational irreducibility, and that for example there will be no fundamentally better way to determine whether a particular branch pair has merged after t steps than by essentially enumerating every possible evolution for that number of steps.

But if this is the case, it means that the general infinite-time question of whether a branch pair will merge is undecidable—and can never be guaranteed to be answerable with a bounded amount of computational effort. It’s a lower bar to ask whether the question can be answered using a finite proof in, say, Peano arithmetic. And I think it’s very likely that the overall question of whether all branch pairs merge—so that the system is confluent—is a statement that can never, for example, be established purely within Peano arithmetic. There are quite a few other candidates for the “simplest ‘numerical’ statement independent of Peano arithmetic”. But it seems at least conceivable that this one might be more accessible to proof than most.

It’s worth mentioning, by the way, that (as we have seen extensively in the Physics Project) the presence of confluence does not imply that a multiway system must show simple overall behavior. Consider for example the rule (also discussed at the end of the previous section):

&#10005


&#10005


Running for a few more steps, removing loose ends and rendering in 3D gives:

&#10005


But despite this complexity, this is a confluent rule. It’s already an indication of this that mergings pretty much “keep up” with branchings in this multiway system:

&#10005


The first few branchings (now all 3-way) are:

&#10005


All the pairs here merge (often somewhat degenerately) in just a few steps. Here are examples of how they work:

&#10005


Branchial Space and Numerical Value Space

Consider the first few steps of the rule

&#10005


&#10005


At each “layer” we can form a branchial graph by joining nodes that have common ancestors on the step before:

&#10005


Continuing for a few more steps we get:

&#10005


We can imagine (as we do in our Physics Project) that in an appropriate (if rather subtle) limit such branchial graphs can be thought of as defining a “branchial space” in which each node has a definite position. (One of many subtleties is that the particular branchial graphs we show here are specific to the particular “layering” of the multiway graph that we’ve used; different foliations would give different results.)

But whereas in our Physics Project and many other applications of the multicomputational paradigm the only real way to define “positions” for nodes in the multiway graph is through something like branchial space, there is a much more direct approach that can be taken in multiway systems based on numbers—because every node is labeled by a number which one can imagine directly using as a coordinate.

As an example, let’s take the multiway graph above, and make the horizontal position of each node be determined by its value:

&#10005


Or, better, by the log of its value:

&#10005


Continuing for more steps, we get:

&#10005


Now, for example, we can ask—given the particular choice of layers we have made here—what the distribution of (logarithmic) values reached on successive layers will be, and one finds that the results converge quite quickly:

&#10005


(By the way, in these results we’ve not included “path weights”, which determine how many different paths lead from the initial number to a particular result. In the example shown, including path weights doesn’t make a difference to the form of the final result.)

So what is the correspondence between the layout of nodes in “branchial space” and in “numerical value space”? Here’s what happens if we lay out a branchial graph using (logarithmic) numerical value as x coordinate:

&#10005


Perhaps more useful is to plot branchial distance versus (logarithmic) numerical distance for every pair of connected nodes at a particular layer:

&#10005


And at least in this case, there is perhaps a slight correlation to be seen.

Negative Numbers

The rules we’ve considered so far all involve only non-negative numbers. What happens if we include negative numbers? Generally the results are very similar to those with non-negative numbers. For example:

&#10005


just gives

&#10005


in which there is effectively both a “positive” and “negative” “web”.

A rule like

&#10005


turns out to yield essentially only positive numbers, yielding after removing loose ends

&#10005


&#10005


gives a more balanced collection of positive and negative numbers (with positive numbers indicated by dark nodes), but the final graph is still quite similar:

&#10005


So far we’ve considered only rules based on ordinary arithmetic functions. As a first example of going beyond that, consider the rule:

&#10005


Running this for 50 steps we get:

&#10005


A notable feature here is that only one “fresh” node is added at each step—and the whole thing grows like a Fermat spiral. After 250 steps the multiway graph has the form

&#10005


which we can readily see is essentially a “binary tree superimposed on a spiral”.

Dividing by 3 instead of 2 makes it a ternary tree:

&#10005


&#10005


Using Round instead of Floor gives a mixed binary and ternary tree:

&#10005


&#10005


What about rules of the form:

&#10005


Here are the results for a few values of a:

&#10005


Continuing

&#10005


for more steps we get:

&#10005


&#10005


has far fewer “loose ends”:

&#10005


What are the “grid patches”? Picking out some of the patches we can see they’re places where a number that can be “halved a lot” appears—and just like in our pure multiplication rules above, and 3n represent commuting operations that form a grid:

&#10005


Conditional Division, Inverse Iterations and the 3n+1 Problem

Including Floor[] is a bit like having different functions for even and odd n. What happens if we do this more explicitly? Consider for example

&#10005


The result is essentially identical to the Floor case:

&#10005


Here are a couple of other cases, at least qualitatively similar to what we’ve seen before:

&#10005


&#10005


&#10005


&#10005


But now consider as we did at the beginning:

&#10005


What is the inverse of this? One can think of it as being

&#10005


or

&#10005


which gives for example

&#10005


or continuing for longer:

&#10005


How about

&#10005


Now the “inverse” is:

&#10005


But in this case since most numbers are not reached in the original iteration, most “don’t have inverses”. However, picking an initial number like 4495, which happens to be a merge point, yields:

&#10005


Note that this “inverse iteration” always monotonically decreases towards 0—reaching it in at most steps.

But now we can compare with the well-known 3n+1 problem, defined by the “singleway” iteration:

&#10005


And while in this case the intermediate numbers sometimes increase, all known initial conditions eventually evolve to a simple cycle:

&#10005


But now we can “invert” the problem, by considering the rule:

&#10005


equivalent to

&#10005


which gives after 10 steps:

&#10005


Continuing this to 25 steps one gets:

&#10005


Removing loose ends this then becomes:

&#10005


or after more steps, and rendered in 3D:

&#10005


The 3n+1 problem now asks whether as the multiway graph is built, it will eventually include every number. But from a multicomputational point of view there are new questions to ask—like whether the “inverse-3n+1-problem” multiway system is confluent.

The first few branchings in the multiway graph in this case are

&#10005


and all of these re-merge after at most 13 steps. The total number of branchings and mergings on successive steps is given by:

&#10005


Including more steps one gets

&#10005


which suggests that there is indeed confluence in this case—though, like for the problem of termination in the original 3n+1 problem, it may be extremely difficult to determine this for sure.

Other Kinds of Rules

All the rules we’ve used so far are—up to conditionals—fundamentally “linear”. But we can also consider “polynomial” rules. With pure powers, as in

&#10005


the multiway graph is just the one associated with the addition of exponents:

&#10005


In a case like

&#10005


the graph is a pure tree

&#10005


while in a case like

&#10005


there is “early merging”, followed by a pure tree:

&#10005


There are also cases like

&#10005


which lead to “continued merging”

&#10005


but when loose ends are removed, they are revealed to behave in rather simple ways:

&#10005


In a case like

&#10005


however, there is at least slightly more complicated merging (shown here after removing loose ends):

&#10005


If we include negative numbers we find cases like:

&#10005


&#10005


But in other “polynomial” cases one tends to get only trees; a merging corresponds to a solution to a high-degree Diophantine equation, and things like the ABC conjecture tend to suggest that very few of these exist.

Returning to the “linear” case, we can consider—as we did above—multiway graphs mod k. Such graphs always have just k nodes. And in a case like

&#10005


with graph

&#10005


they have a simple interpretation—as “remainder graphs” which one can use to compute a given input number n mod k. Consider for example the number 867, with digits 8, 6 and 7. Start at the 0 node. Follow 8 red arrows, followed by a blue one, thus reaching node 3. Then follow 6 red arrows, followed by blue. Then 7 red arrows, followed by blue. The node that one ends up on by this procedure is exactly the remainder. And in this case it is node 6, indicating that Mod[867, 7] is 6.

Not too surprisingly, there is a definite structure to such remainder graphs. Here is the sequence of “binary remainder graphs” generated from the rule

&#10005


for successive values of k:

&#10005


Continuing a number-theoretical theme, we may note that the familiar “divisor graph” for a number can be considered as a multiway graph generated by the rule:

&#10005


Here’s an example for 100:

&#10005


Transitive reduction gives a graph which in this case is essentially a grid:

&#10005


Other initial numbers can give more complicated graphs

&#10005


but in general the transitive reduction is essentially a grid graph of dimension PrimeNu:

&#10005


As an alternative to looking at divisors, we can look, for example, at a rule which transforms any number to the list of numbers relatively prime to it:

&#10005


&#10005


The transitive reduction of this is always trivial, however:

&#10005


One general way to “probe” any function is to look at a multiway graph generated by the rule:

&#10005


Here, for example, is the result for

&#10005


starting with

:

&#10005


Once again, the transitive reduction is very simple:

&#10005


As another example, we can look at:

&#10005


&#10005


where each “efflorescence” corresponds to a prime gap:

&#10005


As a final example we can consider the digit-reversal function:

&#10005


&#10005


&#10005


Non-Integer Values

In almost everything we’ve discussed so far, we’ve been considering only integer values, both in our rules and our initial conditions. So what happens if we start a rule like

&#10005


with a non-integer value? Rather than taking a specific initial value, we can just use a symbolic value x—and it then turns out that the multiway graph is the same regardless of the value of x, integer or non-integer:

&#10005


What if the rule contains non-integer values? In a case like

&#10005


the basic properties of addition ensure that the multiway graph will always have the same grid structure, regardless of a, b and the initial value x:

&#10005


But in a case like

&#10005


things are more complicated. For arbitrary symbolic a, b and initial x, there are no relations that apply, and so the multiway graph is a pure tree:

&#10005


For a specific value of b, however, there are already relations, and a more complicated structure develops:

&#10005


&#10005


Continuing for more steps and removing loose ends we get

&#10005


which is to be compared to the result from above for , :

&#10005


What happens if we choose a non-integer value of b, say:

&#10005


We immediately see that there are “special relations” associated with and its powers:

&#10005


Continuing for longer we get the somewhat complex structure:

&#10005


or in a different rendering with loose ends removed:

&#10005


This structure is very dependent on the algebraic properties of . For a transcendental number like π there are no “special relations”, and the multiway graph will be a tree. For we get

&#10005


and for :

&#10005


Complex Numbers

There are many possible generalizations to consider. An immediate one is to complex integers.

For real numbers always generates a grid. But for example

&#10005


instead generates

&#10005


Continuing for longer, the graph becomes:

&#10005


One feature of having values that are complex numbers is that these values themselves can be used to define coordinates to lay out the nodes of the multiway graph in the plane—giving in this case:

&#10005


or after more steps:

&#10005


Similarly

&#10005


gives

&#10005


The non-branching rule

&#10005


yields

&#10005


while

&#10005


gives

&#10005


If we combine multiplication with addition, we get different forms—and we can make some interesting mathematical connections. Consider rules of the form

&#10005


where c is some complex number. I considered such rules in A New Kind of Science as a practical model of plant growth (though already then I recognized their connection to multiway systems). If we look at the case

&#10005


the multiway graph is structurally just a tree:

&#10005


But if we plot nodes at the positions in the complex plane corresponding to their values we get:

&#10005


Continuing this, and deemphasizing the “multiway edges” we see a characteristic “fractal-like” pattern:

&#10005


Note that this is in some sense dual to the typical “line segment iteration” nested construction:

&#10005


Adding a third “real” branch

&#10005


we get

&#10005


And with

&#10005


the result builds up to a typical Sierpinski pattern:

&#10005


These pictures suggest that at least in the limit of an infinite number of steps there will be all sorts of merging between branches. And indeed it is fairly straightforward to prove this. But what about after, say, t steps?

The result from each branch for the rule

&#10005


is a polynomial such as

&#10005


or

&#10005


So now the question of merging becomes a question of finding solutions to equations which equate the polynomials associated with different possible branches. The simplest nontrivial case equates branch {1, 1} with branch {2, 2}, yielding the equation:

&#10005


with solution

&#10005


We can see this merging in action with the rule:

&#10005


&#10005


The core of what it generates is the repetitive structure:

&#10005


A few additional results are (where the decimals are algebraic numbers of degree 6, and a is a real number):

&#10005


In a case like

&#10005


there is an “early merger”

&#10005


but then the system just generates a tree:

&#10005


The family of rules of the form

&#10005


shows more elaborate behavior. For we get:

&#10005


Continuing for more steps this becomes:

&#10005


For we get instead:

&#10005


If we look at the actual distribution of values obtained by such rules we find for example:

&#10005


If we go beyond multiway systems with pure “1 + c n” rules we soon get results very similar to ones we’ve seen in previous sections. For example

&#10005


gives multiway graph (after removing loose ends)

&#10005


Placing nodes according to their numerical values this then has the form:

&#10005


Collections of Numbers, and Causal Graphs

In studying multiway systems based on complex numbers we’re effectively considering a special case of multiway systems based on collections of numbers. If the complex-number rules are linear, then what we have are iterated affine maps—that form the basis for what I’ve called geometric substitution systems.

As a slightly more general case we can consider multiway systems in which we take pairs of numbers v and apply the rule

&#10005


where now a and b are matrices. If both matrices are the form then this is equivalent to the case of complex numbers. But we can also for example consider a rule like

&#10005


which yields

&#10005


or after more steps and in a different rendering:

&#10005


Laying this out in 2D using the actual pairs of numbers as coordinates, this becomes:

&#10005


Here are samples of typical behavior with 0, 1 matrices:

&#10005


Beyond pure matrix multiplication, we can also consider a rule that adds constant vectors, as in:

&#10005


We can also think in a more “elementwise” way, constructing for example simple rules such as

&#10005


This generates the multiway graph:

&#10005


Continuing for longer and removing loose ends yields:

&#10005


Using values as coordinates then gives:

&#10005


In our Physics Project and other applications of multicomputation, we often discuss causal graphs, that track the causal relationships between updating events. So why is it that these haven’t come up in our discussion of multiway systems based on numbers? The basic reason is that when our states are individual numbers, there’s no reason to separately track updating events and transformations of states because these are exactly the same—because every time a state (i.e. a number) is transformed the number as a whole is “consumed” and new numbers are produced. Or, in other words, the flow of “data” is the same as the flow of “causal information”—so that if we did record events, there’d just be one on each edge of the multiway graph.

But the story is different as soon as our states don’t just contain individual “atomic” things, like single numbers. Because then an updating event can affect just part of a state—and asking what causal relationships there may be between events becomes something separate from asking about the transformation of whole states.

With a rule of the form, say,

&#10005


things are still fairly trivial. Yes, there are separate “x” and “y” events. But they don’t mix, so we’ll just get two independent causal graphs. Things can be less trivial in a case like the one above, of the form:

&#10005


But now there is a different problem. Let’s say that the rule transforms {x, y} to {y + 1, x + 1}. How should we decompose that into “elementary events”? We could say there’s one event that swaps x and y, and others that add 1. Or something different. It’s hard to know.

So why haven’t we encountered this kind of problem in other multicomputational systems, say in hypergraph rewriting systems or string substitution systems? The point is that in these systems the underlying elements always have a certain unique identity, which allows their “flow” to be traced. In our Physics Project, for example, each hypergraph updating event that occurs affects certain particular “atoms of space” (that we can think of as being labeled by unique identifiers)—and so we can readily trace how the effects of different events are related. Similarly, in a string substitution system, we can trace which characters at which positions in the string were affected by a given event, and we can then trace which new characters at which new positions these affect.

But in a system based on numbers this tracing of “unique elements” doesn’t really apply. We might think of 3 as being . But there’s nothing that uniquely tags these 1s, and allows us to trace how they affect 1s that might make up other numbers. In a sense, the whole point of numbers is to abstract away from the labeling of individual objects—and just ask the aggregate question of “how many” there are. So in effect the “packaging” of information into numbers can be thought of as “washing out” causal relationships.

When we give a rule based on numbers what it primarily does is to specify transformations for values. But it’s perfectly possible to add an ancillary “causal rule”, that, for example, can define which elements in an “input” list of numbers should be thought of as being “used as the inputs” to produce particular numbers in an output list of numbers.

There’s another subtlety here, though. The point of a multiway graph is to represent all possible different histories for a system, corresponding to all possible sequences of transformations for states. A particular history corresponds to a particular path in the multiway graph. And if—as in a multiway system based on single numbers—each step in this path is associated with a single, specific event, then the causal graph associated with a particular history will always be trivial.

But in something like a hypergraph- or string-based system there’s usually a nontrivial causal graph even for a single path of history. And the reason is that each transformation between states can involve multiple events—acting on different parts of the state—and there can be nontrivial causal relationships between these events “mediated” by shared elements in the state.

One can think of the resulting causal graph as representing causal relationships in “spacetime”. Successive events define the passage of time. And the layout of different elements in each state can be thought of as defining something like space. But in a multiway system based on single numbers, there isn’t a natural notion of space associated with each state, because the states are just single numbers which “don’t have enough structure” to correspond to something like space.

If we’re dealing with collections of numbers, there’s more possibility of “having something like space”. But it’s easiest to imagine this when one’s dealing with very large collections of numbers, and when the “locations” of the numbers are more important than their values—at which point the fact that they’re numbers (rather than, say, characters in a string) doesn’t make much difference.

But in a multiway system one’s dealing with multiple paths of history, not just one. And one can then start asking about causal relationships not just within a single path of history, but across different paths: a multiway causal graph. And that’s the kind of causal graph we’ll readily construct for a multiway system based on numbers. For a system based on strings or hypergraphs there’s a certain wastefulness to starting with a standard multiway graph of transformations between states. Because if one looks at all possible states, there’s typically a lot of repetition between the “context” of different updating events.

And so an alternative approach is to look just as the “tokens” that are involved in each event: hyperedges in a hypergraph, or runs of characters in a string. So how does it work for a multiway system based on numbers? For this we have to again think about how our states are decomposed for purposes of events, or, in other words, what the “tokens” in them are. And for multiway systems based on single numbers, the natural thing is just to consider each number as a token.

For collections of numbers, it’s less obvious how things should work. And one possibility is to treat each number in the collection as a separate token, and perhaps to ignore any ordering or placement in the collection. We could then end up with a “multi-token” rule like

&#10005


whose behavior we can represent with a token-event graph:

&#10005


But given this, there is then the issue of deciding how collections of tokens should be thought of as aggregated into states. And in general multi-token numerical multiway systems represent a whole separate domain of exploration from what we have considered here.

A basic point, however, is that while our investigations of things like hypergraph and string systems have usually had a substantial “spatial component”, our investigation of multiway systems based on numbers tends to be “more branchial”, and very much centered around the relationships between different branches of history. This does not mean that there is nothing “geometrical” about what is going on. And in fact we fully expect that in an appropriate limit branchial space will indeed have a geometrical structure—and we have even seen examples of this here. It is just that that geometrical structure is—in the language of physics—about the space of quantum states, not about physical space. So this means that our intuition about ordinary physical space won’t necessarily apply. But the important point is that by studying multiway systems based on numbers we can now hope to sharpen our understanding and intuition about things like quantum mechanics.

Much More to Explore…

The basic setup for multiway systems based on numbers is very simple. But what we’ve seen here is that—just like for so many other kinds of systems in the computational universe—the behavior of multiway systems based on numbers can be far from simple.

In many ways, what’s here just scratches the surface of multiway systems based on numbers. There is much more to explore, in many different directions. There are many additional connections to traditional mathematics (and notably number theory) to be made. There are also questions about the geometrical structures that can be generated, and their mathematical characterization.

In the general study of multicomputational systems, branchial—and causal—graphs are important. But here we have barely begun to consider them. A particularly important issue that we haven’t addressed at all is that of alternative possible foliations. In general it has been difficult to characterize these. But it seems possible that in multiway systems based on numbers these may be amenable to investigation with some kind of mathematical techniques. In addition, for things like our Physics Project questions about the coordinatization of branchial space are of great significance—and the “natural coordinatizability” of numbers makes multiway systems based on numbers potentially an attractive place to study these kinds of questions.

Here we’ve considered only ordinary multiway systems, in which the rules always transform one object into several. It’s also perfectly possible to study more general multicomputational systems in which the rules can “consume” multiple objects—and this is particularly straightforward to set up in the case of numbers.

Here we’ve mostly looked at multiway systems whose states are individual integers. But we can consider other kinds of numbers and collections of numbers. We can also imagine generalizing to other kinds of mathematical objects. These could be algebraic constructs (such a polynomials) based on ordinary real or complex numbers. But they could also, for example, be objects from universal algebra. The basic setup for multiway systems—involving repeatedly applying functions—can be thought of as equivalent to repeatedly multiplying by elements (say, generators) of a semigroup. Without any relations between these elements, the multiway graphs we’ll get will always be trees. But if we add relations things can be more complicated.

Multiway systems based on semigroups are in a sense “lower level” than ones based on numbers. In something like arithmetic, one already has immediate knowledge of operations and equivalences between objects. But in a semigroup, these all have to be built up. Of course, if one goes beyond integers, equivalences can be difficult to determine even between numbers (say different representations of radicals or, worse, transcendental numbers).

In their basic construction, multiway systems are fundamentally discrete—involving as they do discrete states, discrete branches, and discrete notions like merging. But in our Physics Project and other applications of the multicomputational paradigm it’s often of interest to think about “continuum limits” of multiway systems. And given that real numbers provide the quintessential example of a continuum one might suppose that by somehow looking at multiway systems based on real numbers one could understand their continuum limit.

But it’s not so simple. Yes, one can imagine allowing a whole “real parameter’s worth” of outputs from the multiway rule. But the issue is how to “knit these together” from one step to the next. The situation is somewhat similar to what happens when one looks at ensembles of random walks, or stochastic partial differential equations. But with multiway systems things are both cleaner and more general. The closest analogy is probably to path integrals of the kind considered in quantum mechanics. And in a sense this is not surprising, because it is precisely the appearance of multiway systems in our Physics Project that seems to lead to quantum mechanics—and in a “continuum limit” to the path integral there.

It’s not clear just how multiway systems are best generalized to the continuum case. But multiway systems based on numbers seem to provide a potentially promising bridge to existing mathematical investigations of the continuum—and I think have a good chance of revealing some elegant and powerful mathematics.

I first looked at multiway systems based on numbers back in the early 1990s, and I always meant to come back and look at them further. But what we’ve found here is that they’re richer and more interesting than I ever imagined. And particularly from what we’ve now seen I expect them to have a very bright future, and for all sorts of important science and mathematics to connect to them, and flow from them.

Thanks

I worked on what’s described here during two distinct periods: May 2020 and September 2021. I thank for help of various kinds Tali Beynon, José Manuel Rodríguez Caballero, Bernat Espigule-Pons, Jonathan Gorard, Eliza Morton, Nik Murzin, Ed Pegg and Joseph Stocke—as well as my weekly virtual high-school “Computational Adventures” group.

×

1 comment

  1. “The 3n+1 problem now asks whether as the multiway graph is built, it will eventually include every number.”

    here is what i came up with using 5 different ranges of seeds..

    seeds 1 to 1024 produces an output of consecutive numbers 1 to 1205
    seeds 1 to 2048 produces an output of consecutive numbers 1 to 2408
    seeds 1 to 4096 produces an output of consecutive numbers 1 to 4814
    seeds 1 to 8192 produces an output of consecutive numbers 1 to 9620
    seeds 1 to 16384 produces an output of consecutive numbers 1 to 19262

    continuing this process .. i don’t see why this would not eventually produce every positive integer ..