Maths

Aggregation and Tiling as Multicomputational Processes—Stephen Wolfram Writings

November 4, 2023

The Significance of Multiway Methods

It’s all about methods the place there can in impact be many attainable paths of historical past. In a typical normal computational system like a cellular automaton, there’s all the time only one path, outlined by evolution from one state to the subsequent. However in a multiway system, there might be many attainable subsequent states—and thus many attainable paths of historical past. Multiway methods have a central role in our Physics Project, significantly in reference to quantum mechanics. However what’s now rising is that multiway methods actually function a fairly basic basis for a complete new “multicomputational” paradigm for modeling.

My goal right here is twofold. First, I wish to use multiway methods as minimal fashions for progress processes based mostly on aggregation and tiling. And second, I wish to use this concrete software as a solution to develop additional instinct about multiway methods usually. Elsewhere I’ve 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. However in learning multiway methods for aggregation and tiling, we’ll be coping with one thing that’s instantly extra bodily and tangible.

After we consider “progress by aggregation” we sometimes think about a “random course of” by which new pieces get added “at random” to one thing. However every of those “random potentialities” in impact defines a special path of historical past. And the idea of a multiway system is to seize all these potentialities collectively. In a typical random (or “stochastic”) mannequin one’s simply tracing a single path of historical past, and one imagines one doesn’t have sufficient info to say which path will probably be. However in a multiway system one’s taking a look at all of the paths. And in doing so, one’s in a way making a mannequin for the “entire story” of what can occur.

The selection of a single path might be “nondeterministic”. However the entire multiway system is deterministic. And by learning that “deterministic entire” it’s typically attainable to make helpful, fairly basic statements.

One can consider a selected second within the evolution of a multiway system as giving one thing like an ensemble of states of the kind studied in statistical mechanics. However the basic idea of a multiway system, with its discrete branching at discrete steps, is dependent upon a stage of elementary discreteness that’s fairly unfamiliar from conventional statistical mechanics—although is completely simple to outline in a computational, and even mathematical, means.

For aggregation it’s straightforward sufficient to set up a minimal discrete model—not less than if one permits express randomness within the mannequin. However a significant level of what we’ll do right here is to “go above” that randomness, establishing our mannequin when it comes to a complete, deterministic multiway system.

What can we be taught by taking a look at this entire multiway system? Properly, for instance, we will see whether or not there’ll all the time be progress—regardless of the random decisions could also be—or whether or not the expansion will typically, and even all the time, cease. And in lots of sensible functions (assume, for instance, tumors) it may be crucial to know whether or not progress all the time stops—or via what paths it will probably proceed.

Lots of what we’ll at first do right here includes seeing the impact of native constraints on progress. Afterward, we’ll additionally have a look at results of geometry, and we’ll examine how objects of various shapes can mixture, or finally tile.

The fashions we’ll introduce are in a way very minimal—combining the best multiway buildings with the best spatial buildings. And with this minimality it’s virtually inevitable that the models will show up as idealizations of all kinds of methods—and as foundations for good fashions of those methods.

At first, multiway methods can appear slightly summary and troublesome to know—and maybe that’s inevitable given our human tendency to think sequentially. However by seeing how multiway methods play out within the concrete case of progress processes, we get to construct our instinct and develop a extra grounded view—that may stand us in good stead in exploring different functions of multiway methods, and usually in coming to phrases with the entire multicomputational paradigm.

The Easiest Case

It’s the final word minimal mannequin for random discrete progress (typically known as the Eden model). On a sq. grid, begin with one black cell, then at every step randomly connect a brand new black cell someplace onto the rising “cluster”:

After 10,000 steps we would get:

However what are all of the attainable issues that may occur? For that, we will assemble a multiway system:

Lots of these clusters differ solely by a trivial translation; canonicalizing by translation we get

or after one other step:

If we additionally cut back out rotations and reflections we get

or after one other step:

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

rising roughly like ok^t for big t, with ok slightly bigger than 4:

By the way in which, canonicalization by translation all the time reduces the variety of attainable clusters by an element of t. Canonicalization by rotation and reflection can cut back the quantity by an element of 8 if the cluster has no symmetry (which for big clusters turns into more and more doubtless), and by a smaller issue the extra symmetry the cluster has, as in:

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

and it doesn’t look any less complicated with various rendering:

If we think about that at every step, cells are added with equal likelihood at each attainable place on the cluster, or equivalently that every one outgoing edges from a given cluster within the uncanonicalized multiway graph are adopted with equal likelihood, then we will get a distribution of chances for the distinct canonical clusters obtained—right here proven after 7 steps:

One characteristic of the massive random cluster we noticed firstly is that it has some holes in it. Clusters with holes begin creating after 7 steps, with the smallest being:

This cluster might be reached via a subset of the multiway system:

And in reality within the restrict of enormous clusters, the likelihood for there to be a gap appears to method 1—though the overall fraction of space coated by holes approaches 0.

One solution to characterize the “house of attainable clusters” is to create a branchial graph by connecting each pair of clusters which have a standard ancestor one step again within the multiway graph:

The connectedness of all these graphs displays the truth that with the rule we’re utilizing, it’s all the time attainable at any step to go from one cluster to a different by a sequence of delete-one-cell/add-one-cell modifications.

The branchial graphs right here additionally present a 4-fold symmetry ensuing from the symmetry of the underlying lattice. Canonicalizing the states, we get smaller branchial graphs that now not present any such symmetry:

Totalistically Constrained Progress (4-Cell Neighborhoods)

With the rule we’ve been discussing thus far, a brand new cell to be hooked up might be anyplace on a cluster. However what if we restrict progress, by requiring that new cells must have certain numbers of existing cells around them? Particularly, let’s contemplate guidelines that have a look at the neighbors round any given place, and permit a brand new cell there provided that there are specified numbers of current cells within the neighborhood.

Beginning with a cross of black cells, listed below are some examples of random clusters one will get after 20 steps with all attainable guidelines of this sort (the preliminary “4” designates that these are 4-neighbor guidelines):

Guidelines that don’t permit new cells to finish up with only one current neighbor can solely fill in corners of their preliminary situations, and may’t develop any additional. However any rule that enables progress with just one current neighbor produces clusters that continue to grow without end. And listed below are some random examples of what one can get after 10,000 steps:

The final of those is the unconstrained (Eden mannequin) rule we already mentioned above. However let’s look extra fastidiously on the first case—the place there’s progress provided that a brand new cell will find yourself with precisely one neighbor. The canonicalized multiway graph on this case is:

The attainable clusters right here correspond to polyominoes which might be “all the time one cell extensive” (i.e. haven’t any 2×2 blocks), or, equivalently, have perimeter 2t + 2 at step t. The variety of such canonicalized clusters grows like:

That is an rising fraction of the overall variety of polyominoes—implying that the majority giant polyominoes take this “spindly” type.

A brand new characteristic of a rule with constraints is that not all places round a cluster might permit progress. Here’s a model of the multiway system above, with cells round every cluster annotated with inexperienced if new progress is allowed there, and purple if it by no means might be:

In a bigger random cluster, we will see that with this rule, many of the inside is “lifeless” within the sense that the constraint of the rule permits no additional progress there:

By the way in which, the clusters generated by this rule can all the time be instantly represented by their “skeleton graphs”:

Taking a look at random clusters for all of the (grow-with-1-neighbor) guidelines above, we see completely different patterns of holes in every case:

There are altogether 5 forms of cells being distinguished right here, reflecting completely different neighbor configurations:

Right here’s a pattern cluster generated with the 4:{1,3} rule:

Cells indicated with have already got too many neighbors, and so can by no means be added to the cluster. Cells indicated with have precisely the fitting variety of neighbors to be added instantly. Cells indicated with don’t at present have the fitting variety of neighbors to develop, but when neighbors are crammed in, they may be capable to be added. Generally it would end up that when neighbors of cells get crammed in, they are going to truly stop the cell from being added (in order that it turns into )—and within the specific case proven right here that occurs with the two×2 blocks of cells.

The multiway graphs from the principles proven listed below are all qualitatively comparable, however there are detailed variations. Particularly, not less than for most of the guidelines, an rising variety of states are “lacking” relative to what one will get with the grow-in-all-cases 4:{1,2,3,4} rule—or, in different phrases, there are an rising variety of polyominoes that may’t be generated given the constraints:

The primary polyomino that may’t be reached (which happens at step 4) is:

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

whereas for 4:{1} and 4:{1,4} the extra polyomino

may also not be reached.

At step 8, the polyomino

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

Of some observe is that not one of the guidelines that exclude polyominoes can attain:

Totalistically Constrained Progress (8-Cell Neighborhoods)

What occurs if one considers diagonal as properly orthogonal neighbors, giving a complete of 8 neighbors round a cell? There are 256 attainable guidelines on this case, comparable to the attainable subsets of Range[8]. Listed below are samples of what they do after 200 steps, ranging from an preliminary cluster:

Two instances that not less than initially present progress listed below are (the “8” designates that these are 8-neighbor guidelines):

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

One may assume that each department on this graph would proceed without end, and that progress would by no means “get caught”. Nevertheless it seems that after 9 steps the next cluster is generated:

And with this cluster, no additional progress is feasible: no positions across the boundary have precisely 2 neighbors. Within the multiway graph as much as 10 steps, it seems that is the one “terminal cluster” that may be generated—out of a complete of 1115 attainable clusters:

So how is that terminal cluster reached? Right here’s the fragment of multiway graph that results in it:

If we don’t prune off all of the methods to “go astray”, the fragment seems as half of a bigger multiway graph:

And if one follows all paths within the unpruned (and uncanonicalized) multiway graph at random (i.e. at every step, one chooses every department with equal likelihood), it seems that the likelihood of ever reaching this specific terminal cluster is simply:

(And the truth that this quantity is pretty small implies that the system is way from confluent; there are lots of paths that, for instance, don’t converge to the fastened level comparable to this terminal cluster.)

If we preserve going within the evolution of the multiway system, we’ll attain different terminal clusters; after 12 steps the next have appeared:

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

As soon as once more there are terminal clusters the place the system will get caught; the primary of them seems at step 14:

And in addition as soon as once more the terminal cluster seems as an remoted node in the entire multiway system:

The fragment of multiway graph that results in it’s:

Up to now we’ve been discovering terminal clusters by ready for them to seem within the evolution of the multiway system. However there’s one other method, just like what one may use in filling in something like a tiling. The thought is that each cell in a terminal cluster will need to have neighbors that don’t permit additional progress. In different phrases, the terminal cluster should include sure “native tiles” for which the constraints don’t permit progress. However what configurations of native tiles are attainable? To find out this, we flip the matching situations for the tiles into logical expressions whose variables are True and False relying on whether or not specific positions within the template do or don’t comprise cells within the cluster. By fixing the satisfiability problem for the mixture of those logical expressions, one finds configurations of cells that might conceivably correspond to terminal clusters.

Following this process for the {2} guidelines with areas of as much as 6×6 cells we discover:

However now there’s a further constraint. Assuming one begins from a linked preliminary cluster, any subsequent cluster generated should even be linked. Eradicating the non-connected instances we get:

So given these terminal clusters, what preliminary situations can result in them? To find out this we successfully should invert the aggregation process—giving ultimately a multiway graph that features all preliminary situations that may generate a given terminal cluster. For the smallest terminal cluster we get:

Our 4-cell “T” preliminary situation seems right here—however we see that there are additionally even smaller 2-cell preliminary situations that result in the identical terminal cluster.

For all of the terminal clusters we confirmed earlier than, we will assemble the multiway graphs beginning with the minimal preliminary clusters that result in them:

For terminal clusters like

there’s no nontrivial multiway system to indicate, since these clusters can solely seem as preliminary situations; they’ll by no means be generated within the evolution.

There are fairly just a few small clusters that may solely seem as preliminary situations, and should not have preimages beneath the aggregation rule. Listed below are the instances that slot in a 3×3 area:

The case of the {3} rule is pretty just like the {2} rule. The attainable terminal clusters as much as 5×5 are:

Nevertheless, most of those have solely a reasonably restricted set of attainable preimages:

For instance we’ve got:

And certainly past the (size-17) instance we already confirmed above, no different terminal clusters that may be generated from a T preliminary situation seem right here. Sampling additional, nevertheless, further terminal clusters seem (starting at dimension 25):

The fragments of multiway graphs for the primary few of those are:

Random Evolution

We’ve seen above that for the principles we’ve been investigating, terminal clusters are fairly uncommon amongst attainable states within the multiway system. However what occurs if we simply evolve at random? How typically will we wind up with a terminal cluster? After we say “evolve at random”, what we imply is that at every step we’re going to have a look at all attainable positions the place a brand new cell may very well be added to the cluster that exists thus far, after which we’re going to choose with equal likelihood at which of those to really add the brand new cell.

For the 8:{3} rule one thing shocking occurs. Although terminal clusters are uncommon in its multiway graph, it seems that no matter its preliminary situations, it all the time finally reaches a terminal cluster—although it typically takes some time. And right here, for instance, are a few possible terminal clusters, annotated with the variety of steps it took to achieve them (which can be equal to the variety of cells they comprise):

The distribution of the variety of steps to termination appears to be very roughly exponential (right here based mostly on a pattern of 10,000 random instances)—with imply lifetime round 2300 and half-life round 7400:

Right here’s an instance of a giant terminal cluster—that takes 21,912 steps to generate:

And right here’s a map exhibiting when progress in several components of this cluster occurred (with blue being earliest and purple being newest):

This image means that completely different components of the cluster “actively develop” at completely different occasions, and if we have a look at a “spacetime” plot of the place progress happens as a perform of time, we will verify this:

And certainly what this means is that what’s occurring is that completely different components of the cluster are at first “fertile”, however later inevitably “burn out”—in order that ultimately there aren’t any attainable positions left the place progress can happen.

However what shapes can the ultimate terminal clusters type? We will get some thought by taking a look at a “compactness measure” (of the sort typically used to check gerrymandering) that roughly offers the usual deviation of the distances from the middle of every cluster to every of the cells in it. Each “very stringy” and “roughly round” clusters are pretty uncommon; most clusters lie someplace in between:

If we glance not on the 8:{3} however as a substitute on the 8:{2} rule, issues are very completely different. As soon as once more, it’s attainable to achieve a terminal cluster, because the multiway graph exhibits. However now random evolution virtually by no means reaches a terminal cluster, and as a substitute virtually all the time “runs away” to generate an infinite cluster. The clusters generated on this case are sometimes far more “compact” than within the 8:{3} case

and that is additionally mirrored within the “spacetime” model:

Parallel Progress and Causal Graphs

In build up our clusters thus far, we’ve all the time been assuming that cells are added sequentially, one after the other. But when two cells are far sufficient aside, we will truly add them “concurrently”, in parallel, and find yourself constructing the identical cluster. We will consider the addition of every cell as being an “occasion” that updates the state of the cluster. Then—identical to in our Physics Mission, and different functions of multicomputation—we will outline a causal graph that represents the causal dependencies between these occasions, after which foliations of this causal graph inform us attainable general sequences of updates, together with parallel.

For example, contemplate this sequence of states within the “all the time develop” 4:{1,2,3,4} rule—the place at every step the cell that’s new is coloured purple (and we’re together with the “nothing” state firstly):

Each transition between successive states defines an occasion:

There’s then causal dependence of 1 occasion on one other if the cell added within the second occasion is adjoining to the one added within the first occasion. So, for instance, there are causal dependencies like

and

the place within the second case further “spatially separated” cells have been added that aren’t concerned within the causal dependence. Placing all of the causal dependencies collectively, we get the whole causal graph for this evolution:

We will get well our authentic sequence of states by choosing a selected ordering of those occasions (right here indicated by the positions of the cells they add):

This path has the property that it all the time follows the path of causal edges—and we will make that extra apparent by utilizing a special structure for the causal graph:

However usually we will use any ordering of occasions in line with the causal graph. One other ordering (out of a complete of 40,320 potentialities on this case) is

which supplies the sequence of states

with the identical last cluster configuration, however completely different intermediate states.

However now the purpose is that the constraints implied by the causal graph don’t require all occasions to be utilized sequentially. Some occasions might be thought-about “spacelike separated” and so might be utilized concurrently. And in reality, any foliation of the causal graph defines a sure sequence for making use of occasions—both sequentially or in parallel. So, for instance, right here is one specific foliation of the causal graph (proven with two completely different renderings for the causal graph):

And right here is the corresponding sequence of states obtained:

And since in some slices of this foliation a number of occasions occur “in parallel”, it’s “sooner” to get to the ultimate configuration. (Because it occurs, this foliation is sort of a “cosmological relaxation body foliation” in our Physics Mission, and includes the utmost attainable variety of occasions occurring on every slice.)

Completely different foliations (and there are a complete of 678,972 potentialities on this case) will give completely different sequences of states, however all the time the identical last state:

Be aware that nothing we’ve finished right here is dependent upon the actual rule we’ve used. So, for instance, for the 8:{2} rule with sequence of states

the causal graph is:

It’s value commenting that all the pieces we’ve finished right here has been for specific sequences of states, i.e. specific paths within the multiway graph. And in impact what we’re doing is the analog of classical spacetime physics—tracing out causal dependencies particularly evolution histories. However usually we might have a look at the entire multiway causal graph, with occasions that aren’t solely timelike or spacelike separated, but additionally branchlike separated. And if we make foliations of this graph, we’ll find yourself not solely with “classical” spacetime states, but additionally “quantum” superposition states that may must be represented by one thing like multispace (by which at every spatial place, there’s a “branchial stack” of attainable cell values).

The One-Dimensional Case

Up to now we’ve been contemplating aggregation processes in two dimensions. However what about one dimension? In 1D, a “cluster” simply consists of a sequence of cells. The only rule permits a cell to be added at any time when it’s adjoining to a cell that’s already there. Ranging from a single cell, right here’s a attainable random evolution in line with such a rule, proven evolving down the web page:

We will additionally assemble the multiway system for this rule:

Canonicalizing the states offers the trivial multiway graph:

However identical to within the 2D case issues get much less trivial if there are constraints on progress. For instance, assume that earlier than inserting a brand new cell we rely the variety of cells that lie both distance 1 or distance 2 away. If the variety of allowed cells can solely be precisely 1 we get conduct like:

The corresponding multiway system is

or after canonicalization:

The variety of distinct sequences after t steps right here is given by

which might be expressed when it comes to Fibonacci numbers, and for big t is about .

The rule in impact generates all attainable Morse-code-like sequences, consisting of runs of both 2-cell (“lengthy”) black blocks or 1-cell (“quick”) black blocks, interspersed by “gaps” of single white cells.

The branchial graphs for this technique have the shape:

Taking a look at random evolutions for all attainable guidelines of this sort we get:

The corresponding canonicalized multiway graphs are:

The foundations we’ve checked out thus far are purely totalistic: whether or not a brand new cell might be added relies upon solely on the overall variety of cells in its neighborhood. However (very like, for instance, in mobile automata) it’s additionally possible to have rules the place whether or not one can add a brand new cell is dependent upon the whole configuration of cells in a neighborhood. Principally, nevertheless, such guidelines appear to behave very very like totalistic ones.

Different generalizations embody, for instance, guidelines with a number of “colours” of cells, and guidelines that rely both on the overall variety of cells of various colours, or their detailed configurations.

The Three-Dimensional Case

The type of evaluation we’ve finished for 2D and 1D aggregation methods can readily be prolonged to 3D. As a primary instance, contemplate a rule by which cells might be added alongside every of the 6 coordinate instructions in a 3D grid at any time when they’re adjoining to an current cell. Listed below are some typical examples of random clusters fashioned on this case:

Taking successive slices via the primary of those (and coloring by “age”) we get:

If we permit a cell to be added solely when it’s adjoining to only one current cell (comparable to the rule 6:{1}) we get clusters that from the skin look virtually indistinguishable

however which have an “airier” inner construction:

Very similar to in 2D, with 6 neighbors, there can’t be unbounded progress except cells might be added when there is only one cell within the neighborhood. However in analogy to what occurs in 2D, issues get extra sophisticated after we permit “nook adjacency” and have a 26-cell neighborhood.

If cells might be added at any time when there’s not less than one adjoining cell, the outcomes are just like the 6-neighbor case, besides that now there might be “corner-adjacent outgrowths”

and the entire construction is “nonetheless airier”:

Little qualitatively modifications for a rule like 26:{2} the place progress can happen solely with precisely 2 neighbors (right here beginning with a 3D dimer):

However the basic query of when there may be progress, and when not, is kind of sophisticated and refined. Particularly, even with a selected rule, there are sometimes some preliminary situations that may result in unbounded progress, and others that can’t.

Generally there may be progress for some time, however then it stops. For instance, with the rule 26:{9}, one attainable path of evolution from a 3×3×3 block is:

The complete multiway graph on this case terminates, confirming that no unbounded progress is ever attainable:

With different preliminary situations, nevertheless, this rule can develop for longer (right here proven each 10 steps):

And from what one can inform, all guidelines 26:{n} result in unbounded progress for , and don’t for .

Polygonal Shapes

Up to now, we’ve been taking a look at “filling in cells” in grids—in 2D, 1D and 3D. However we will additionally have a look at simply “inserting tiles” with out a grid, with every new tile attaching edge to edge to an current tile.

For sq. tiles, there isn’t actually a distinction:

And the multiway system is simply the identical as for our authentic “develop anyplace” rule on a 2D grid:

Right here’s now what occurs for triangular tiles:

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

And since equilateral triangles can tessellate in a daily lattice, we will consider this—just like the sq. case—as “filling in cells in a lattice” slightly than simply “inserting tiles”. Listed below are some bigger examples of random clusters on this case:

Basically the identical occurs with common hexagons:

The multiway graph generates all polyhexes:

Listed below are some examples of bigger clusters—exhibiting considerably extra “tendrils” than the triangular case:

And in an “successfully lattice” case like this we might additionally go on and impose constraints on neighborhood configurations, a lot as we did in earlier sections above.

However what occurs if we contemplate shapes that don’t tessellate the aircraft—like common pentagons? We will nonetheless “sequentially place tiles” with the constraint that any new tile can’t overlap an current one. And with this rule we get for instance:

Listed below are some “randomly grown” bigger clusters—exhibiting all kinds of irregularly formed interstices inside:

(And, sure, producing such photos accurately is way from trivial. Within the “successfully lattice” case, coincidences between polygons are pretty straightforward to find out precisely. However in one thing just like the pentagon case, doing so requires fixing equations in a high-degree algebraic number field.)

The multiway graph, nevertheless, doesn’t present any instantly apparent variations from those for “successfully lattice” instances:

It makes it barely simpler to see what’s happening if we riffle the outcomes on the final step we present:

The branchial graphs on this case have the shape:

Right here’s a bigger cluster fashioned from pentagons:

And keep in mind that the way in which that is constructed is sequentially so as to add one pentagon at every step by testing each “uncovered edge” and seeing by which instances a pentagon will “match”. As in all our different examples, there isn’t any desire given to “exterior” versus “inner” edges.

Be aware that whereas “successfully lattice” clusters all the time finally fill in all their holes, this isn’t true for one thing just like the pentagon case. And on this case it seems that within the restrict, about 28% of the general space is taken up by holes. And, by the way in which, there’s a particular “zoo” of not less than small attainable holes, right here plotted with their (logarithmic) chances:

So what occurs with different common polygons? Right here’s an instance with octagons (and on this case the limiting whole space taken up by holes is about 35%):

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

With pentagons, it’s fairly clear that difficult-to-resolve geometrical conditions will come up. And one may need thought that octagons would keep away from these. However there are nonetheless loads of unusual “mismatches” like

that aren’t straightforward to characterize or analyze. By the way in which, one ought to observe that any time a “closed gap” is fashioned, the vectors comparable to the perimeters that type its boundary should sum to zero—in impact defining an equation.

When the variety of sides within the common polygon will get giant, our clusters will approximate circle packings. Right here’s an instance with 12-gons:

However in fact as a result of we’re insisting on including one polygon at a time, the ensuing construction is way “airier” than a real circle packing—of the sort that may be obtained (not less than in 2D) by “pushing on the perimeters” of the cluster.

Polyomino Tilings

Within the earlier part we thought-about “sequential tilings” constructed from common polygons. However the strategies we used are fairly basic, and might be utilized to sequential tilings fashioned from any form—or shapes (or, not less than, any shapes for which “attachment edges” might be recognized).

As a primary instance, contemplate a domino or dimer form—which we assume might be oriented each vertically and horizontally:

Right here’s a considerably bigger cluster fashioned from dimers:

Right here’s the canonicalized multiway graph on this case:

And listed below are the branchial graphs:

So what about different polyomino shapes? What occurs after we attempt to sequentially tile with these—successfully making “polypolyominoes”?

Right here’s an instance based mostly on an L-shaped polyomino:

Right here’s a bigger cluster

and right here’s the canonicalized multiway graph after simply 1 step

and after 2 steps:

The one different 3-cell polyomino is the tromino:

(For dimers, the limiting fraction of space coated by holes appears to be about 17%, whereas for L and tromino polyominoes, it’s about 27%.)

Going to 4 cells, there are 5 attainable polyominoes—and listed below are samples of random clusters that may be constructed with them (observe that within the final case proven, we require solely that “subcells” of the two×2 polyomino should align):

The corresponding multiway graphs are:

Persevering with for extra steps in just a few instances:

Some polyominoes are “extra awkward” to suit collectively than others—so these sometimes give clusters of “decrease density”:

Up to now, we’ve all the time thought-about including new polyominoes in order that they “connect” on any “uncovered edge”. And the result’s that we will typically get lengthy “tendrils” in our clusters of polyominoes. However an alternate technique is to attempt to add polyominoes as “compactly” as attainable, in impact by including successive “rings” of polyominoes (with “older” rings right here coloured bluer):

On the whole there are lots of methods so as to add these rings, and finally one will typically get caught, unable so as to add polyominoes with out leaving holes—as indicated by the purple annotation right here:

In fact, that doesn’t imply that if one was ready to “backtrack and check out once more”, one couldn’t discover a solution to lengthen the cluster with out leaving holes. And certainly for the polyomino we’re taking a look at right here it’s completely attainable to finish up with “excellent tilings” by which no holes are left:

On the whole, we might contemplate all kinds of various methods for rising clusters by including polyominoes “in parallel”—identical to in our dialogue of causal graphs above. And if we add polyominoes “a hoop at a time” we’re successfully making a selected selection of foliation—by which the successive “ring states” end up be instantly analogous to what we name “generational states” in our Physics Project.

If we permit holes (and don’t impose different constraints), then it’s inevitable that—simply with abnormal, sequential aggregation—we will develop an unboundedly giant cluster of polyominoes of any form, simply by all the time attaching one edge of every new polyomino to an “uncovered” fringe of the prevailing cluster. But when we don’t permit holes, it’s a special story—and we’re speaking a few conventional tiling drawback, the place there are finally instances the place tiling is unattainable, and solely limited-size clusters might be generated.

Because it occurs, all polyominoes with 6 or fewer cells do permit infinite tilings. However with 7 cells the next don’t:

It’s completely attainable to develop random clusters with these polyominoes—however they have an inclination to not be in any respect compact, and to have numerous holes and tendrils:

So what occurs if we attempt to develop clusters in rings? Listed below are all of the attainable methods to “encompass” the primary of those polyominoes with a “single ring”:

And it turns that in each single case, there are edges (indicated right here in purple) the place the cluster can’t be prolonged—thereby demonstrating that no infinite tiling is feasible with this specific polyomino.

By the way in which, very like we noticed with constrained progress on a grid, it’s attainable to have “tiling areas” that may lengthen solely a sure restricted distance, then always get stuck.

It’s value mentioning that we’ve thought-about right here the case of single polyominoes. It’s additionally attainable to think about with the ability to add a whole set of possible polyominoes—“Tetris type”.

Nonperiodic Tilings

We’ve checked out polyominoes—and shapes like pentagons—that don’t tile the aircraft. However what about shapes that may tile the aircraft, however solely nonperiodically? For example, let’s contemplate Penrose tiles. The fundamental shapes of those tiles are

although there are further matching situations (implicitly indicated by the arrows on every tile), which might be enforced both by placing notches within the tiles or by adorning the tiles:

Beginning with these particular person tiles, we will construct up a multiway system by attaching tiles wherever the matching guidelines are glad (observe that every one edges of each tiles are the identical size):

So how can we inform that these tiles can type a nonperiodic tiling? One method is to generate a multiway system by which at successive steps we encompass clusters with rings in all attainable methods:

Persevering with for one more step we get:

Discover that right here a number of the branches have died out. However the query is what branches exist that may proceed without end, and thus result in an infinite tiling? To reply this we’ve got to do a bit of research.

Step one is to see what attainable “rings” can have fashioned across the authentic tile. And we will learn all of those off from the multiway graph:

However now it’s handy to look not at attainable rings round a tile, however as a substitute at attainable configurations of tiles that may encompass a single vertex. There seems to be the next restricted set:

The final two of those configurations have the characteristic that they’ll’t be prolonged: no tile might be added on the middle of their “blue sides”. Nevertheless it seems that every one the opposite configurations might be prolonged—although solely to make a nested tiling, not a periodic one.

And a primary indication of that is that bigger copies of tiles (“supertiles”) might be drawn on high of the primary three configurations we simply recognized, in such a means that the vertices of the supertiles coincide with vertices of the unique tiles:

And now we will use this to assemble guidelines for a substitution system:

Making use of this substitution system builds up a nested tiling that may be continued without end:

However is such a nested tiling the one one that’s attainable with our authentic tiles? We will show that it’s by exhibiting that each tile in each attainable configuration happens inside a supertile. We will pull out attainable configurations from the multiway system—after which in every case it seems that we will certainly discover a supertile by which the unique tile happens:

And what this all means is that the one infinite paths that may happen within the multiway system are ones that correspond to nested tilings; all different paths should finally die out.

The Penrose tiling includes two distinct tiles. However in 2022 it was discovered that—if one’s allowed to flip the tile over—only a single (“hat”) tile is adequate to drive a nonperiodic tiling:

The complete multiway graph obtained from this tile (and its flip-over) is sophisticated, however many paths in it lead (not less than finally) to “lifeless ends” which can’t be additional prolonged. Thus, for instance, the next configurations—which seem early within the multiway graph—all have the property that they’ll’t happen in an infinite tiling:

Within the first case right here, we will successively add just a few rings of tiles:

However after 7 rings, there’s a “contradiction” on the boundary, and no additional progress is feasible (as indicated by the purple annotations):

Having eradicated instances that all the time result in “lifeless ends” the ensuing simplified multiway graph successfully contains all joins between hat tiles that may finally result in surviving configurations:

As soon as once more we will define a supertile transformation

the place the area outlined in purple can probably overlap one other supertile. Now we will assemble a multiway graph for the supertile (in its “bitten out” and full variant)

and may see that there’s a (one-to-one) map from the multiway graph for the unique tiles and for these supertiles:

And now from this we will inform that there might be arbitrarily giant nested tilings utilizing the hat tile:

Private Notes

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

And in some ways the present piece is a three-decade-later followup to that observe—utilizing a brand new method based mostly on multiway methods.

In A New Form of Science I did discuss multiway systems (each abstractly, and in connection with fundamental physics). However what I stated about aggregation was principally in a piece known as “The Phenomenon of Continuity” which mentioned how randomness might on a big scale result in obvious continuity. That part started by speaking about issues like random walks, however went on to debate the same minimal (“Eden model”) instance of “random aggregation” that I give right here. After which, in an try and “spruce up” my dialogue of aggregation, I began taking a look at “aggregation with constraints”. In the primary textual content of the e book I gave simply two examples:

However then for the footnote I studied a wider vary of constraints (enumerating them a lot as I had mobile automata)—and observed the shocking phenomenon that with some constraints the aggregation course of might find yourself getting caught, and never with the ability to proceed.

For years I carried across the thought of investigating that phenomenon additional. And it was typically on my record as a attainable challenge for a scholar to discover on the Wolfram Summer School. Often it was picked, and progress was made in numerous instructions. After which just a few years in the past, with our Physics Mission within the offing, the thought arose of investigating it utilizing multiway methods—and there have been Summer time College initiatives that made progress on this. In the meantime, as our Physics Mission progressed, our tools for working with multiway systems significantly improved—finally making attainable what we’ve finished right here.

By the way in which, again within the Nineties, one of many many subjects I studied for A New Form of Science was tilings. And in an effort to find out what tilings have been attainable, I investigated what quantities to aggregation under tiling constraints—which is actually even a generalization of what I contemplate right here:

Thanks

At first, I’d prefer to thank Brad Klee for in depth assist with this piece, in addition to Nik Murzin for extra assist. (Thanks additionally to Catherine Wolfram, Christopher Wolfram and Ed Pegg for particular pointers.) I’d prefer to thank numerous Wolfram Summer time College college students (and their mentors) who’ve labored on aggregation methods and their multiway interpretation lately: Kabir Khanna 2019 (mentors: Christopher Wolfram & Jonathan Gorard), Lina M. Ruiz 2021 (mentors: Jesse Galef & Xerxes Arsiwalla), Pietro Pepe 2023 (mentor: Bob Nachbar). (Additionally associated are the Summer time College initiatives on tilings by Bowen Ping 2023 and Johannes Martin 2023.)